1012)유기농 배추2(DFS)

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

삼성 역테 준비할 겸 DFS 배우고 관련 문제 조지려 한다.

이 문제를 처음 풀었을 때 내가 문제를 푼 방식이 DFS인 줄도 모르고 풀었다.

FM DFS와는 차이가 있긴 했지만 DFS의 변형인 것은 분명했다.

원래 DFS는 연결 그래프를 빠짐 없이 방문하는 순회 알고리즘이다.

그러나 DFS는 그래프만 다룰 수 있는 것이 아니라 배열도 순회할 수 있다.

그래프의 관점에서 배열을 바라보는 것이다.

2차원 배열의 격자 공간 하나하나가 노드이고 인접한 방끼리 연결되어있다 생각하면 편하다.

그렇다고 해서 배열의 방 갯수만큼 인접리스트나 인접행렬을 만드는 것은 좋은 방법이 아니다.

예를들어 4x4 배열을 DFS로 순회할 때 16개의 노드를 방문해야 한다.

그렇다면 16x16 크기의 인접 행렬이나 노드 갯수가 16개인 인접 리스트를 만들어야 할까?

그렇지 않다. 어차피 배열은 바로 옆이나 위, 아래의 방과 인접하기 때문에 현재 방을 기준으로 상하좌우의 방만 방문하면 된다.

유기농 배추 문제를 푸는 방법은 배열의 모든 방을 접근할 때 현재 방이 true라면 그 지점에서 DFS로 현재 연결 요소를 순회한 뒤 빠져 나온다.

이후 count를 하나 증가시키면 모든 연결 요소의 수를 셀 수 있다.

#include<iostream>
using namespace std;
 
bool area[50][50] = { false };
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
 
void dfs(int x, int y) {
    int nextX, nextY;
 
    area[x][y] = false;
    for (int i = 0; i< 4;i++) {
        nextX = x + dx[i];
        nextY = y + dy[i];
        if (!(0<=nextX &&  nextX<50))continue;
        if (!(0 <= nextY && nextY < 50))continue;
        if(area[nextX][nextY]) dfs(nextX,nextY);
    }
}
 
int main() {
    int t;
    int m, n, k;
    int x, y;
    
    cin >> t;
    while (t--) {
        cin >> m >> n >> k;
        for (int i = 0; i < k; i++) {
            cin >> x >> y;
            area[x][y] = true;
        }
 
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j< n; j++) {
                if (area[i][j]) {
                    dfs(i, j);
                    count++;
                }
            }
        }
        cout << count << endl;
    }
    
    return 0;
}