[Baekjoon] 2667번 단지번호붙이기.cpp

[백준] 2667번 단지번호붙이기 문제 링크

해당 문제는 bfs를 이용해 해결하였다. 스택을 사용하는 dfs로도 풀 수 있지만 재귀 형태의 dfs로는 메모리 초과 때문에 해결할 수 없음에 유의하자.

이 문제에서 신경쓸 것은 배열 입력 및 범위 제한, 오름차순 정렬이다. 문제에서 이걸 못 보고 몇 분이나 헤매고 있었다. 문제를 잘 읽도록 하자. 또한 각 단지에 포함된 집의 수를 배열로 관리했었는데 자꾸 틀려서 벡터로 바꾸니 해결되었다. 이유는 모르겠다.

그 외에는 단지를 구분하기 위해 해당 인덱스에 집이 존재하는지, 그곳에 미리 방문했는지 확인하는 작업을 큐에 삽입하기 전에 해준다는 것만 신경써서 풀면 그리 어려운 문제가 아니다.

근데 왜 1시간이나 걸려서 풀었는지 모르겠다. 실버 1 문젠데..

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>

std::pair<int, int> direction[4] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

int estateNum;
int graph[25][25];
int visit[25][25];

std::vector<int> estates;
int houseCnt;

std::queue<std::pair<int, int>> q;

void bfs(int x, int y){
    visit[x][y] = 1;
    while(!q.empty()){
        std::pair<int, int> cur = q.front();
        q.pop();
        houseCnt++;

        for(auto dir : direction){
            int nextX = cur.first + dir.first;
            int nextY = cur.second + dir.second;

            if(nextX < 0 || nextX >= estateNum || nextY < 0 || nextY >= estateNum){
                continue;
            }
            if(graph[nextX][nextY] == 1 && visit[nextX][nextY] == 0){
                q.push({nextX, nextY});
                visit[nextX][nextY] = 1;
            }
        }
    }
}

int main(){
    scanf("%d", &estateNum);
    for(int col = 0; col < estateNum; col++){
        std::string tmp;
        std::cin >> tmp;
        for(int index = 0; index < tmp.length(); index++){
            graph[col][index] = tmp[index] - '0';
        }
    }

    for(int col = 0; col < estateNum; col++){
        for(int row = 0; row < estateNum; row++){

            if(graph[col][row] == 1 && visit[col][row] == 0){
                q.push({col, row});
                bfs(q.front().first, q.front().second);
                estates.push_back(houseCnt);
                houseCnt = 0;
            }
        }
    }
    printf("%d\n", estates.size());
    std::sort(estates.begin(), estates.end());
    for(int count = 0; count < estates.size(); count++){
        printf("%d\n", estates[count]);
    }
}