1012 번 유기농배추 (DFS)

본문제는 

DFS 를 활용하는 가장 간당한 문제이다.

DFS 는 보통 재귀함수를 사용하여 사용하는데. 

재귀함수로 여러번 호출해서 사용하게되면 프로그램 속도가 늦쳐질 수 있기 때문에, 

STL 에서 stack 을이용해 구현해보았다. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include<iostream> #include<stack> #include<vector> #include<memory.h> using namespace std;   stack<pair<int, int>> S; vector<vector<bool>> V; void CHECK(int x, int y){     if (x > 0 && V[x - 1][y] == true){         S.push(pair<int,int>(x - 1, y));         V[x - 1][y] = false;     }     if (x+1 <50  && V[x+1][y] == true){         S.push(pair<int, int>(x + 1, y));         V[x + 1][y] = false;     }     if (y > 0 && V[x][y-1] == true){         S.push(pair<int, int>(x , y-1));         V[x][y-1] = false;     }     if (y+1<50 && V[x][y+1] == true){         S.push(pair<int, int>(x, y+1));         V[x][y+1] = false;     }   } int main(){     int T, M, N, K;     int cnt;     cin >> T;     while (T--){         V.clear();         cin >> M >> N >> K;         V.assign(M+1, vector<bool>(N+1, false));         cnt = 0;         while (K--){             int x, y;             cin >> x >> y;             V[x][y] = true;         }         for (int i = 0; i < M; i++){             for (int j = 0; j < N; j++){                 if (V[i][j] == true){                     cnt++;                     CHECK(i,j);                     V[i][j] = false;                     while (!S.empty()){                         pair<int, int> temp = S.top();                         S.pop();                         CHECK(temp.first, temp.second);                     }                 }             }         }         cout <<cnt<<endl;     }     return 0; }