백준 2667 : 단지 번호 붙이기

문제 링크입니다 https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

DFS와 BFS 중 어느 것이든 상관없는 문제였습니다. BFS를 통해 문제를 해결했고, 해결 절차는 다음과 같습니다.

 

[1] 입력받은 지도를 훑으면서 집이 있고, 동시에 아직 방문하지 않은 집이라면 해당 좌표부터 BFS를 시작합니다.

[2] BFS 함수를 통해 연결되어있는 집이 몇 개인지 파악하고 반환해줍니다.

[3] 반환받은 값을 배열에 저장하고, 다시 1번으로 돌아갑니다.

 

이렇게 반복하여 모든 집을 방문하게 되면 집이 몇 개인지를 저장한 배열을 오름차순으로 정렬한 후, BFS를 몇 번 호출 했는지 (단지가 몇 개인지) 출력하고 각 단지별 집의 개수(정렬한 배열의 값)를 순서대로 출력하면 됩니다.

 

 

[소스코드]

 

#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 25 + 10;
 
bool check[MAX][MAX];  // 방문 처리를 할 check 배열
 
// 단지의 개수를 나타낼 ret, 집의 개수를 저장할 result
int n, map[MAX][MAX], ret, result[MAX*MAX];
 
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,-1,0,1 };
 
// [2] (y, x)부터 bfs를 통해 연결된 집의 개수를 세어서 반환하는 함수
int bfs(int y, int x) {
 
    queue <pair<int, int> > q;
 
    int cnt = 0;         // 집의 개수를 세어줄 변수
    check[y][x] = true;  // 방문 처리
    q.push(make_pair(y, x));
 
    while (!q.empty()) {
        // 현재 좌표의 y값, x값을 꺼냅니다
        int cury = q.front().first, curx = q.front().second;
        
        // pop을 한 후, 집의 개수를 늘려줍니다
        q.pop(), cnt++;
 
        // 상, 하, 좌, 우를 모두 확인하면서
        for (int i = 0; i < 4; i++) {
            
            // 다음 칸을 결정하고
            int yy = cury + dy[i], xx = curx + dx[i];
 
            // 그 칸을 이미 방문했거나, 그곳이 집이 아니거나
            // 그 칸이 배열을 벗어났으면 
            if (check[yy][xx] || !map[yy][xx] || yy < 0 || yy >= n || xx < 0 || xx >= n)
                continue;  // 위로 올라갑니다
            
            q.push(make_pair(yy, xx));  // 집인 칸을 큐에 넣고
            check[yy][xx] = true;       // 방문 처리
        }
    }
    return cnt;  // [2] 집의 개수 반환
}
 
int main(void) {
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            // 띄어쓰기가 되지 않은 입력이므로 1d로 받아주면
            // 숫자 하나씩 입력 받을 수 있습니다
            scanf("%1d", &map[i][j]);
 
    // [1] 지도를 훑으면서
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            // [1] 해당 좌표의 값이 0이 아니고 아직 방문하지 않았으면 bfs
            if (map[i][j] && !check[i][j])
                result[ret++] = bfs(i, j); // [3] 반환 받은 값을 배열에 저장
 
    sort(result, result + ret);  // 배열을 오름차순으로 정렬합니다
 
    // ret 값은 결국 0부터 bfs가 실행될때마다 1씩 증가하므로
    // 최종적으로 단지의 개수가 됩니다
    printf("%d\n", ret);
 
    // 그래서 i는 0부터 ret 까지 : 단지의 개수만큼
    for (int i = 0; i < ret; i++)
        printf("%d\n", result[i]);
 
    return 0;
}