백준[1012] - 유기농 배추

문제

백준 1012 문제 보기

접근 방법

dfs 방식을 활용하면 문제를 해결할 수 있다. 배추가 존재한다면 인접한 곳에 배추가 있는지 확인하는 방식으로 문제를 풀수 있다.

코드

#include <iostream>
#include <cstring>

using namespace std;

int T, M, N, K;
int map[51][51];
int visited[51][51];
// 북, 동, 남, 서 (시계 방향)
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int dfs(int r, int c) {
    // 좌표에서 시계방향으로 검사
    for(int i = 0; i < 4; i ++) {
        int nextR = r + dr[i];
        int nextC = c + dc[i];
        // map 안에 존재하는 범위
        if(nextC >= 0 && nextR >= 0 && nextC < N && nextR < M) {
            // 배추가 존재하고 방문하지 않았다면
            if(map[nextR][nextC] && !visited[nextR][nextC]) {
                // 방문 체크
                visited[nextR][nextC] = 1;
                // 다음 좌표
                dfs(nextR, nextC);
            }
        }
    }
    return 0;
}

int main() {
    cin >> T;
    while(T--) {
        memset(map, 0, sizeof(map));
        memset(visited, 0, sizeof(visited));
        cin >> M >> N >> K;
        for(int i = 0; i < K; i ++) {
            int r, c;
            cin >> r >> c;
            map[r][c] = 1;
        }
        int ans = 0;
        for(int i = 0; i < M; i ++) {
            for(int j = 0; j < N; j ++) {
                if(map[i][j] && !visited[i][j]) {
                    visited[i][j] = 1;
                    dfs(i, j);
                    ans ++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}