[DFS] 백준 1012번 - 유기농 배추 (정답률 34%)

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

1012번: 유기농 배추

백준 DFS 연습 문제이다.

주어진 밭의 정보에서 배추들의 '군' 개수를 dfs 탐색으로 찾는 문제였다.

 

각 테스트 케이스마다 밭에 배추군이 몇 개 있는지 dfs탐색으로 쉽게 할 수 있었다. 백트래킹도 필요없는 쉬운 문제였다.

 

아래는 소스코드 (0ms)

#include <iostream>
#define maxlen 50
using namespace std;
int T, C, R, K;
bool check[maxlen][maxlen];
int map[maxlen][maxlen];
int answer = 0;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void reset(){
    for (int i = 0; i < maxlen; i++){
        for (int j = 0; j < maxlen; j++){
            check[i][j] = false;
            map[i][j] = 0;
        }
    }
}
 
void dfs(int r, int c){
    check[r][c] = true;
    for (int i = 0; i < 4; i++){
        int n_r = r + direction[i].dr;
        int n_c = c + direction[i].dc;
        if (n_r >= 0 && n_r < R && n_c >= 0 && n_c < C){
            // 범위 내에 있고,
            if (!check[n_r][n_c] && map[n_r][n_c]){
                // 배추가 존재하며 아직 방문하지 않은 경우, 방문해라.
                dfs(n_r, n_c);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    reset();
    cin >> T;
    for (int i = 0; i < T; i++){
        cin >> C >> R >> K; // 가로, 세로, 배추개수.
        int vegi_r, vegi_c;
        
        for (int j = 0; j < K; j++){
            cin >> vegi_c >> vegi_r; // 가로, 세로 순으로 입력!
            map[vegi_r][vegi_c] = 1;
        }
 
        // map에 배추위치 넣음. 이제 배추군의 개수로 이 케이스의 정답 찾기.
        for (int r = 0; r < R; r++){
            for (int c = 0; c < C; c++){
                if (!check[r][c] && map[r][c]){
                    dfs(r, c);
                    answer++;
                }
            }
        }
        cout << answer << '\n';
        reset(); // check, map 초기화.
        answer = 0; // 답 초기화
    }
    return 0;
}