[BOJ] 백준 1012 유기농 배추

백준 1012 유기농 배추

문제링크 : https://www.acmicpc.net/problem/1012

보통 DFS/BFS는 미로탐지에 쓰입니다.

이 문제도 그렇습니다. 비록 전체 배열이 하나의 미로는 아니지만, 배열을 Divide 해 보면 부분적으로는 미로 입니다. 즉, 하나의 공간이 1, 즉 갈수 있는 길이면 거기서부터 미로가 시작되어 끝까지 가고, 끝까지 갔을때 지렁이의 개수를 하나 추가해 주면 되는 문제 입니다.

소스 코드 :

#include 
#include 
#include 
using namespace std;


int main() {
 int num;
 cin >> num; cin.ignore();
 while (num--) {
  int m, n, baechu;
  cin >> m >> n >> baechu; cin.ignore();
  // 가로 세로 각각 1줄씩 더 추가하여 둘러쌓음.
  vector< vector > v(m+2, vector(n+2, 0));
  for (int i = 0; i < baechu; i++) {
   int a, b;
   cin >> a >> b; cin.ignore();
   // 가로 세로 각각 1줄씩 추가하였으므로 벡터에 입력시 +1 해줌.
   v[a+1][b+1] = 1;
  }
  stack> stack;
  int dragon = 0;
  for (int i = 1; i < m + 1; i++) {
   for (int j = 1; j < n + 1; j++) {
    if (v[i][j] == 1) {
     v[i][j] = 2; // visited
     stack.push(pair{i, j});
     while (!stack.empty()) {
      int f = stack.top().first;
      int s = stack.top().second;
      stack.pop();
      if (v[f - 1][s] == 1) { // West 
       v[f - 1][s] = 2; // visited;
       stack.push(pair{f - 1, s});
      }
      if (v[f][s - 1] == 1) { // North
       v[f][s - 1] = 2; // visited;
       stack.push(pair{f, s - 1});
      }
      if (v[f][s + 1] == 1) { // South
       v[f][s + 1] = 2; // visited;
       stack.push(pair{f, s + 1});
      }
      if (v[f + 1][s] == 1) { // East
       v[f + 1][s] = 2; // visited;
       stack.push(pair{f + 1, s});
      }
     }
     dragon++; // 지렁이 추가
    } // if end
   }
  } // for end
  cout << dragon << endl;
 } // while end
}