BOJ 1113

11 Feb 2020 • ProblemSolving

수영장만들기

문제출처

문제 해석

  • N*M크기의 땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는 지 구하는 문제입니다.
  • 각 블록에는 벽의 높이 정보가 주어지며, 물은 벽의 높이가 높은곳에서 낮은 곳으로 흐릅니다.

설계(X)

  • 첫번째로 수영장을 만들 수 있는 조건은 해당 높이(h)보다 큰 높이에 둘러싸여 있어야 합니다. 이 조건을 생각해보았으나 아이디어를 얻지 못해 해당 블로그를 참조하였습니다.
  • 첫번째 조건을 만족하기 위해서는 4방향으로 조사를 했을 때, 범위를 벗어나면 안되는 것입니다.
  • 9보다 작거나 같은 높이를 1부터 순차적으로 조사를 할때, height(기준높이)보다 작거나 같은 좌표를 탐색하도록 합니다.
  • 만약 범위를 벗어나면 dfs탐색을 하는동안 방문했던 곳들을 이전 상태로 되돌려 놓습니다.
  • 모든 좌표에 대해서 탐색을 마치면, 방문표시가 된 곳만 dist 배열에 갱신합니다.
  • 기준 높이 9까지 탐색을 마치면 저장된 dist를 모두 더한 값이 정답이 됩니다.

구현(50)

코드
#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 50

int map[MAXN][MAXN];
int dist[MAXN][MAXN];
bool visited[MAXN][MAXN];
bool tmp[MAXN][MAXN];
int N,M;
int height;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool flag;
void dfs(int x,int y){
    if (flag) return;
    visited[x][y] =true;
    for (int k =0 ;k<4;k++){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || ny < 0||nx>=N||ny>=M){
            flag = true;
            return;
        }
        if (!visited[nx][ny] && map[nx][ny] <= height){
            dfs(nx,ny);
        }
    }
    
}
int main(){
    
    scanf("%d%d",&N,&M);
    for (int i = 0; i<N;i++){
        for (int j=0;j<M;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    height = 1;
    while (height <= 9){
        memset(visited,false,sizeof(visited));
        for (int i = 0; i < N; i++){
            for (int j = 0;j < M; j++){
                flag = false;
                memcpy(tmp,visited,sizeof(visited));
                if (!visited[i][j] && map[i][j] <= height){
                    dfs(i,j);
                }
                if (flag){
                    memcpy(visited,tmp,sizeof(tmp));
                }
            }
        }
        for (int i =0 ; i<N;i++){
            for (int j=0;j<M;j++){
                dist[i][j] += visited[i][j];
            }
        }
        height++;
    }
    int ans = 0;
    for (int i = 0 ;i<N;i++){
        for (int j=0;j<M;j++){
            ans+=dist[i][j];
        }
    }
    printf("%d\n",ans);
    return 0;
}
디버깅
  • 제출결과가 다른 분들에 비해 현저히 느리게 나온이유를 찾기 위해 공개코드 처리된 juno님의 코드를 참조해 보았습니다.
  • 저는 범위를 벗어난 경우를 되돌리는 구현을 하기 위해서 이전 방문상태를 저장해 놓았습니다. 이로 인해 O(NM^2)이라는 시간복잡도가 되어 느리게 나온 것으로 생각됩니다.
  • juno님은 갈수있는(기준높이보다 작은) 블록들의 정보를 방문체크를 먼저 해 놓고, dfs탐색을 return값을 int형으로 주어 범위를 벗어날 경우 0을 리턴하게 설정을 해주었습니다.
  • 이를 통해 O(NM)으로 구현이 가능하고, 또한 ans를 직접 더하기 때문에 별도로 더해주는 작업을 해주지 않아도 되게 최적화가 되었습니다.
제출결과
  • 232ms

마무리

  • dfs또는 bfs탐색을 이용하여 해결할 수 있는 문제였습니다. 최적화 유무에 따라서 제출결과에 미치는 영향이 크다는 것을 실감했습니다.
 BOJ

Related Posts