1012번 유기농 배추 탐색

진짜 오랫동안 풀었습니다..

처음에는 BFS를 활용하여 풀어야 한다 생각하고,

그렇게 계속 풀다가 잘못생각했다는것을 알아었다.

왜냐하면 문제를 푸는 도중..

모두 탐색하고 방문했던 인덱스를 무시하는 방법만이 붙어있는 배추를 지렁이를 둘 하나의 공간으로 세는 것이 가능한 방법이었다는 사실을 알아냈기 때문이다.

그래서 DFS를 활용하여 풀어보았다..

이 문제 꼭 풀어보고 싶었는데.. 여기까지 온 것이 행복하고 신기하다..

이건 내 친구 동훈이 덕분에 잘 풀어내었다.

백준 링크는 아래와 같다 이 알고리즘을 풀어내었다!!!!

기분은 좋다.

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

1012번: 유기농 배추

#include <stdio.h>

int vis[51][51] = {0};
int arr[51][51] = {0};
int N, M, P;
int dx[4] = {1,-1, 0, 0};
int dy[4] = {0, 0, 1, -1};



void DFS(int y, int x) {
    int next_x, next_y;
    for(int o=0; o<4; o++) {
        next_x = dx[o]+x;
        next_y = dy[o]+y;
        if(next_x < 0 || next_x >=M || next_y <0 || next_y >=N) {
            continue ;
        }
        if(arr[next_y][next_x] && !vis[next_y][next_x]) {
            vis[next_y][next_x] = 1;
            DFS(next_y, next_x);
        }
    }
}

int main() {
    int x, y, T, cnt;
    scanf("%d", &T);
    while(T) {
        scanf("%d %d %d", &M, &N, &P);
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                arr[i][j] = 0;
                vis[i][j] = 0;
            }
        }
        cnt = 0;
        for(int i=0; i<P; i++) {
            scanf("%d %d", &x, &y);
            arr[y][x] = 1;
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(arr[i][j] && !vis[i][j]) {
                    vis[i][j] = 1;
                    cnt+=1;
                    DFS(i, j);
                }
            }
        }
        printf("%d\n", cnt);
        T-=1;
    }
}