백준 #1012 유기농 배추 (c++)

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

1012번: 유기농 배추

사실 이 문제는 저번 학기에 학회 초급 알고리즘 과정 막바지쯤에 풀었어야 했던 문젠데

내 기억으로 그때 전공 과제(아마 객체였던걸로 기억..) + 기말고사 준비기간 때문에 시도했었다가 못 풀었던 문제다.

 

그때 들었던 bfs와 dfs 강의도 사실 이해는 했지만 그 내용을 완전히 흡수하지 못했기에 시도를 했음에도 풀지 못했던 것 같다.

그렇지만 지금의 나는 자료구조 수업에서까지 dfs를 마스터(?)한 상태였기에 코드를 조금조금씩 짜볼 수 있었다.

 

일단 이 문제는 앞에서도 방금 언급했듯이, dfs(깊이 우선 탐색) 또는 bfs(너비 우선 탐색)를 사용하는 문제다.

알고리즘을 조금이라도 해본 사람이라면 무조건 한번쯤은 들어봤을 알고리즘인데

간단히 설명하자면

 

dfs는 depth-first search로, 말 그대로 깊이 우선 탐색이다.

반대로 bfs는 breadth-first search, 즉 너비 우선 탐색이다.

이진 트리 예시

처음에 말로만 들었을땐 이해가 잘 안 갈 수도 있기에 위의 이진 트리를 예시로 각각 dfs와 bfs를 했을 때 어떤 결과가 나오는지 살펴보자.

 

둘 다 노드 A에서 시작한다고 했을 떄,

 

dfs : A B D C E G F H I

bfs : A B C D E F G H I

 

와 같은 방식으로 탐색이 진행될 것이다.

 

각각의 탐색방식을 선으로 표현해봤을 때, dfs는 주로 세로 방향으로 bfs는 주로 가로 방향으로 진행된다는 것을 볼 수 있다.

굳이 한글로 표현하자면 dfs는 하나를 쭉 파고 들어가는 방식, bfs는 두루두루 찬찬히 살펴보는 방식 정도로 설명할 수 있겠다.

---

그러면 다시 문제로 돌아가보자.

문제에서 나온 예시1

일단 나는 이 문제를 dfs로 풀었는데 사실 bfs로도 풀이가 가능하다고 하니 나중에 한번 bfs로도 풀어볼 계획이다.

 

dfs의 관점은 아까도 말했듯이 하나를 쭉 파는 방식이기 때문에 그림의 2차원 배열을 왼쪽에서 오른쪽으로, 위에서 아래로 보되,

1이 나올때마다 인접한 모든 1들을 묶어버릴 것이다.

ex) (0,0) (1,0) (1,1)를 한 덩어리로, (4,2) (4,3)을 한 덩어리로 ...

 

+ dfs는 그 좌표에서 인접한 좌표로, 그리고 그 좌표에서 인접한 또 다른 좌표로 계속 이동하는 방식이기 때문에 재귀함수의 형식을 사용한다.

 

그러나 그렇게 1들을 묶어내는 과정에서 내가 이쪽 1은 이미 탐색했다는걸 표시해야하는데,

우선 그 이유는 2차원 배열을 쭉 둘러보는 과정에서 중복 탐색하는걸 방지하기 위해서다.

 

그 방법 중 가장 일반적인 방법은 bool visited[50][50]로 dfs로 탐색을 끝낼 때마다 그 좌표의 원소값을 true로 바꿔주는 방법이다.

 

그러나 나는 다른 방법을 사용해서 문제를 풀어봤는데, 그것은 바로

양배추가 있는 자리를 1로 표시해놓은 밭(2차원 배열)을 그 양배추를 dfs로 탐색할 때마다 그 좌표의 원소값을 0으로 바꿔주는 방법이다.

2차원 배열을 쭉 훑어보면서 애초에 우리는 양배추가 있는 1 자리만 탐색할 것이기 때문에 이미 탐색한 자리를 0으로 바꿔놓으면

중복 탐색할 일은 절대 일어나지 않을 것이다.

 

이 방법을 사용하여 코드를 짜봤는데 나는 단순히 2차원 배열을 왼쪽에서 오른쪽으로, 위에서 아래로 탐색하니까

dfs로 1들을 묶어내는 과정에서 현재 좌표의 오른쪽과 아래쪽을 보도록 코드를 짰는데, 이상하게 그 코드를 제출했더니 틀렸습니다가 떴다.

 

결국 각 좌표의 동서남북을 모두 살피는 방식으로 코드를 수정하니 바로 맞았습니다가 떴는데 아무리 생각해도 이전에 코드에서 나올 수 있는 반례가 떠오르지 않아 친구에게 물어봤었는데, 그 친구가 말하길 양배추(1)가 늘어져 있는 모양이 U자라면 어떻게 되겠냐고 했다.

그 말을 듣자마자 아차 싶었다. 그래도 내가 원했던 반례를 알아내서 답답했던 마음이 조금 뚫리는 것 같았다.

---

예전에는 마냥 어렵게 느껴졌던 dfs 문제였는데, 그떄와 달리 생각보다 쉽게? 이 문제를 풀어낸 것 같아서 확실히 성장했다는 느낌을 받을 수 있었다. (아마 자료구조 수업 때문이겠지?) 앞으로도 dfs bfs 문제들을 더 풀어서 문제 유형을 더 익히고 차근차근 마스터할 것이다.

 

(제출한 코드)

#include <iostream>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;

int T;
int M, N, K;
int cabbage[55][55];
int di[] = {-1,1,0,0};
int dj[] = {0,0,1,-1};

void dfs(int i, int j) {
  cabbage[i][j] = 0;
  for(int k=0; k<4; k++) {
    int ni = i + di[k];
    int nj = j + dj[k];
    if(ni>=0 && ni<N && nj>=0 && nj<M)
      if(cabbage[ni][nj]==1) dfs(ni,nj);
  }
}

int main() {
  FASTIO;
  cin >> T;
  while(T--) {
    cin >> M >> N >> K;
    for(int i=0; i<K; i++) {
      int x, y; cin >> x >> y;
      cabbage[y][x] = 1;
    }
    int cnt = 0;
    for(int i=0; i<N; i++) {
      for(int j=0; j<M; j++) {
        if(cabbage[i][j]==1) {
          cnt++;
          dfs(i,j);
        }
      }
    }
    cout << cnt << '\n';
  }
}