[BOJ] 1012번. 유기농 배추

문제 링크 : https://www.acmicpc.net/problem/1012

문제는 링크 참고.

풀이.

이 문제는 딱 보고 생각나는 데로 풀면된다.

배추가 있는 부분을 찾아 그 부분의 갯수를 세어 출력하면 배추 흰 애벌레가 얼마나 필요한지 알 수 있다.

입력된 좌표를 돌면서 1을 찾았을 때, 그 부분의 1을 DFS를 이용하여 다 없애버리고 cnt ++을 하면된다.

여기서 시간을 좀 더 빠르게 하고 싶다면 입력된 좌표 갯수 만큼만 탐색을 하여 부분을 찾으면 조금 더 시간이 빨라질 수 있다.

(우리가 인지할 만큼 빨라지지 않음)

#include <stdio.h>
#include <memory.h>
 
#define MAX 50
 
bool map[MAX + 1][MAX + 1] = {0};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int Xs[MAX * MAX + 1] = {0}, Ys[MAX * MAX + 1] = {0};
int T = 0, M = 0, N = 0, K = 0, X = 0, Y = 0, cnt = 0;
 
void DFS(int x, int y) {
    int tx = 0, ty = 0;
     
    map[x][y] = false;
    
    for (int i = 0 ; i < 4; i ++) {
        tx = x + dx[i];
        ty = y + dy[i];        
        if (tx >= 0 && tx < M && ty >= 0 && ty < N && map[tx][ty])
            DFS(tx, ty);
    }
}
 
int main() {
    scanf("%d", &T);
    
    while (T--) {
        cnt = 0;
        scanf("%d %d %d", &M, &N, &K);
        
        for (int i = 0 ; i < K ; i ++) {
            scanf("%d %d", &X, &Y);
            
            map[X][Y] = true;
            Xs[i] = X;
            Ys[i] = Y;
        }
        
        for (int i = 0 ; i < K ; i ++) {
            X = Xs[i];
            Y = Ys[i];
            if (map[X][Y]) {
                cnt ++;
                DFS(X, Y);
            }
        }
        
        printf("%d\n", cnt);
        
        memset(map, false, sizeof(map));
    }
    
    return 0;
}

참고사항.

백준에서 푸는데 49번 째 줄을 printf("%d", cnt);로 하고 제출을 하니 답이 틀렸다고 나온다.

앞으로는 출력할 때 개행열(\n)을 붙히는 습관을 들이자.