[BOJ][C++] 1012 유기농배추

[BOJ][C++] 1012 유기농배추

 

문제

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

 

풀이

DFS를 이용해서 풀었습니다. 배추가 있는 곳을 체크한 후 깊이 탐색을 합니다. 깊이탐색을 시작할 때 한 번 카운팅을 해준 후 인접한 곳의 배추들은 카운팅을 하지 않고 visited를 바꿔줍니다.

visited가 1인 곳은 다시 방문하지 않고 다시 메인함수로 와서 방문하지 않은 다른 배추 위치를 찾습니다. 이를 반복하면 수월하게 풀 수 있습니다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
int M, N, K;
int map[50][50];
int visited[50][50];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
void reset() {
    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            map[i][j] = 0;
            visited[i][j] = 0;
        }
    }
}
void CountingWorm(int x, int y) {
    visited[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
        if (map[nx][ny] == 1 && visited[nx][ny] == 0) {
            CountingWorm(nx, ny);
        }
    }
}
int main() {
    int T;
    scanf("%d", &T);

    for (int t = 1; t <= T; t++) {
        reset();
        scanf("%d %d %d", &M, &N, &K);
        for (int k = 0; k < K; k++) {
            int tmp1, tmp2;
            scanf("%d %d", &tmp1, &tmp2);
            map[tmp1][tmp2] = 1;
        }
        
        int cnt = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && visited[i][j] == 0) {
                    cnt++;
                    CountingWorm(i, j);
                }
            }
        }
        printf("%d\n", cnt);
    }
}