/<> 백준 2667번 : 단지번호붙이기 (C언어)

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

 

 

BFS를 이용해 단지 경로를 추적하고, 끝까지 이동할 수 없는 경우 이 경로를 하나의 단지로 간주합니다. 그다음 해당 단지의 집의 수를 저장하면 됩니다. 그러기 위해선 단지의 개수를 인덱스로 가지고 집의 수를 값으로 가지는 배열을 따로 추가해 주면 됩니다.

 

 

1. 지도를 입력받습니다. 지도의 숫자들이 붙어있으므로 문자열로 간주하고 반복문을 통해 하나씩 배열에 저장해줍니다.

 

2. 방문 여부 배열, 단지의 정보를 저장하는 배열을 생성합니다.

 

3. 너비 우선 탐색(BFS)을 이용해 지도를 탐색합니다. 시작 좌표를 기준으로 탐색을 실행하기에 시작 좌표를 인자로 받는 함수를 만들었습니다.

 

4. 더 이상 이동할 수 없는 경우, 단지 배열의 인덱스를 추가하고 거기에 해당 집의 수를 저장합니다.

 

5. 단지 배열을 오름차순으로 정렬한 후 집의 수를 차례로 출력합니다.

 

 

<코드>

#include <stdio.h>

int n;
int map[25][25];
int visit[25][25] = {0,};
int group[500];
int group_count = 0;

int move_x[4] = {1, -1, 0, 0};
int move_y[4] = {0, 0, 1, -1}; 

int bfs(int x, int y) {
    int count = 1;
    int qX[625], qY[625], front = 0, rear = 0;
    qX[rear] = x;
    qY[rear++] = y;
    
    visit[x][y] = 1;
    while(front < rear) {
        int cX = qX[front];
        int cY = qY[front++];
        
        for(int i = 0; i < 4; i++) {
            int nX = cX + move_x[i];
            int nY = cY + move_y[i];
            
            if(nX >= 0 && nX < 25 && nY >= 0 && nY < 25 && !visit[nX][nY] && map[nX][nY]) {
                qX[rear] = nX;
                qY[rear++] = nY;
                visit[nX][nY] = 1;
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        char input[n+1];
        scanf("%s", input);
        
        for(int j = 0; j < n; j++) map[i][j] = input[j] - '0';
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(map[i][j] && !visit[i][j]) group[group_count++] = bfs(i, j);
        }
    }

    for(int i = 0; i < group_count - 1; i++) {
        for(int j = i + 1; j < group_count; j++) {
            if(group[i] > group[j]) {
                int temp = group[i];
                group[i] = group[j];
                group[j] = temp;
            }
        }
    }

    printf("%d\n", group_count);
    for(int i = 0; i < group_count; i++) printf("%d\n", group[i]);
    return 0;
}