[백준/BOJ] 16946 벽 부수고 이동하기 4 - 접근과 풀이 (c++)

https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

벽 부수고 이동하기 시리즈 마지막 문제

---

접근 방법

 

이 문제는 1.2.3 번 문제의 코드와 연관이 없는 문제다. 특정 벽을 부술 때 연결된 칸 수를 구한다. 

가장 먼저 떠오르는 풀이는 모든 벽을 부숴보고 bfs/dfs를 돌리는건데, K개의 벽이 있다고 할 때 시간 복잡도가 O(NMK)가 될 것이 자명하므로 시도하지 않는다.

 

bfs/dfs를 최소한으로 사용하는 경우를 생각 해 보니, N*M의 맵에서 dfs/bfs를 이용하여 존재하는 공간에 대해서 크기를 미리 계산한다. 그리고 모든 벽에 대해서, 벽을 부숨으로 인해 생기는 4방향의 크기만 더해주면 될 것 같았다. 그렇게 하면 O(c*NM) 시간 안에 해결이 된다. 아마 c는 8?

 

벽을 부수기 전 dfs 전처리를 할 때,

1. N*M 크기의 새로운 배열에 해당 칸의 계산된 크기(dfs를 하여 나온 크기를 해당하는 칸에 모두 저장)를 저장하는 방법과

2. dfs를 하여 계산된 크기를 (index - cnt)으로 벡터에 따로 저장하고, N*M 크기의 새로운 배열에 해당 칸의 index로만 채우는 방법

 

두 가지를 고민했다. 1번 방법은 dfs를 두 번 돌려야 해서 코드가 길어질 것 같아서 포기하고, 2번 방법으로 접근했다. 결론적으로 4방향을 조사할 때 같은 공간인 경우 한번만 더해주어야 하는데, 이 때 c++의 set 라이브러리를 사용하여 index값을 저장하여 효과적으로 해결해서 좋은 선택이 되었다.

 

---

풀이

 tag : bfs/dfs

#include<iostream>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
int N,M;
int arr[1001][1001];
int idx=0;
vector<int> cntVector;
int cnt=0;

int visited[1001][1001]={0};
int idxArr[1001][1001];

const int dy[4]={-1,0,1,0};
const int dx[4]={0,1,0,-1};

int dfs(int r,int c,int idx){ //빈칸인곳들 크기 계산 // 센 개수 반환
  cnt++;
  idxArr[r][c]=idx;
  visited[r][c]=1;
  for(int i=0;i<4;i++){
    int nr=r+dy[i];
    int nc=c+dx[i];
    if(nr<0 || nc<0 || nr>=N || nc >=M)
      continue;
    if(arr[nr][nc]==0 && visited[nr][nc]==0)
      dfs(nr,nc,idx);
  }
  return cnt;
}
int main(){
  memset(idxArr,-1,sizeof(idxArr));
  cin>>N>>M; 
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      scanf("%1d",&arr[i][j]);
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      if(visited[i][j]==0 && arr[i][j]==0){
        cnt=0;
        int tmp=dfs(i,j,idx++);
        cntVector.push_back(tmp);
      }
    }
  }

 for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      int sum=0;
      if(arr[i][j]==1){  //벽이면 부수자
        set<int> set; //중복제거
        sum+=1;
        for(int k=0;k<4;k++){
          int nr=i+dy[k];
          int nc=j+dx[k];
          if(nr<0 || nc<0 || nr>=N || nc >=M || arr[nr][nc]==1)
            continue;
          set.insert(idxArr[nr][nc]);
        }
        for(int i : set){
          sum+=cntVector[i];
        }
      }
      printf("%d",sum%10);
    }
    printf("\n");
  }
}

코드를 간결하게 짜는데 중점을 두면, 전역변수를 많이 사용하게 되는데, 좋은건지 나쁜건지 모르겠다