[BFS/DFS] C11 백준 1012 유기농 배추 풀이

문제

• 1012

풀이 과정

• 배추 흰지렁이가 어떤 배추에 하나 있으면 인접한 다른 배추로 이동 가능 -> 이어져있는 영역으로 이동 가능, bfs 냄새가 난다!
• 심지어 이동도 상하좌우 네 방향으로 간다고 하네? 확신
• 근데 들어오는 값이 맵 전체 값이 아니고 배추 심어져있는 위치 좌표로 들어오기 때문에 맵 배열 하나 두고 좌표대로 1 찍어주고 bfs 돌면서 카운팅
  • 그림 영역 세는거와 같은 원리로 카운팅
• 쉬운 문제였으나... 디버깅에도 안 보이는 부분이 있었으니(ㅠㅠ)
  • 이 문제는 여러개의 tc가 있기 때문에 초기화가 중요한데, 큐도 꼭! 초기화 하도록 하자.. front, rear 초기화 안해서 틀렸다..

#include <stdio.h>

#define MAX 51

typedef struct Que {
    int x;
    int y;
} Q;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int n,m,k;
int map[MAX][MAX];
int visit[MAX][MAX];

Q que[MAX*MAX];
int front;
int rear;

void enqueue(int x, int y) {
    que[rear].x = x;
    que[rear].y = y;
    rear++;
}

Q dequeue() {
    return que[front++];
}

void bfs() {
    while (front < rear) {
        Q cur = dequeue();
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
               map[nx][ny] == 1 && visit[nx][ny] == 0) {
                visit[nx][ny] = 1;
                enqueue(nx, ny);
            }
        }
    }
}

int main() {
    int tc;
    scanf("%d", &tc);
    
    while (tc--) {
        scanf("%d %d %d", &m, &n, &k);
        
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                map[i][j] = 0;
                visit[i][j] = 0;
            }
        }
        
        for (int i=0; i<k; i++) {
            int x, y = 0;
            scanf("%d %d", &x, &y);
            map[y][x] = 1;
        }
        
        int bug = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (map[i][j] == 1 && visit[i][j] == 0) {
                    bug++;
                    
                    visit[i][j] = 1;
                    enqueue(i, j);
                    bfs();
                }
            }
        }
        printf("%d\n", bug);
        
        front = 0;
        rear = 0;
    }
    
    return 0;
}