[백준 2667] - 단지번호붙이기

문제

• <그림 1>과 같이 정사각형 모양의 지도가 있다.
• 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
• 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.
• 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말하며, 대각선상에 집이 있는 경우는 연결된 것이 아니다.
• <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.
• 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에는 지도의 크기 N (정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25) 이 입력된다.
• 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

• 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

솔루션

• 먼저 지도를 처음 부터 끝까지 다 훑는다.
• 0인 부분인 건너 뛰고, 1인 부분을 찾았다면 해당 지점부터 BFS를 수행한다.
• 동, 서, 남, 북으로 확인하며 집을 찾을 때 (값이 1인 지점) 마다 집 갯수를 늘려준다.
• 단지 내 집을 모두 찾았다면, 단지 내 집 갯수를 반환한다.
• 결과적으로 area 벡터에 단지 별 집 갯수가 모두 들어가 있을 것이며, 단지의 갯수는 area 벡터의 크기와 같을 것이다.

 

Code

• 전체 코드 : Dange Numbering

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
    {
        if (!visited[i][j] && map[i][j] != 0)      // 아직 방문하지 않은 단지 집이 있다면
            area.push_back(DangeNumbering(i, j));  // 단지 내부 집의 갯수를 세기 위해 (BFS) 함수 실행
    }                                              // 그리고 반환 값으로 단지 집 갯수를 받아 벡터에 저장
}
 
sort(area.begin(), area.end());                    // 오름차순으로 정렬

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};         // 동, 서, 남, 북 지점으로 나아갈 연산좌표
 
int DangeNumbering(int x, int y)
{
    queue<pair<int, int> > queue;
    int count = 1;                                        // 단지의 첫 집을 찾았으므로 1부터 시작
 
    visited[x][y] = true;                                 // 처음 지점 방문 표시
    queue.push(make_pair(x, y));                          // 큐에 삽입
 
    while (!queue.empty())
    {
        pair<int, int> temp = queue.front();
        queue.pop();
 
        for (int i = 0; i < 4; i++)
        {
            nx = dx[i] + temp.first;                      // 다음 지점 x좌표
            ny = dy[i] + temp.second;                     // 다음 지점 y좌표
 
            if (0 <= nx && nx < N && 0 <= ny && ny < N)   // 다음 좌표가 지도 내부에 있는지
            {
                if (!visited[nx][ny] && map[nx][ny] != 0) // 방문 하지 않았고 다음 좌표가 집이 있는지
                {
                    queue.push(make_pair(nx, ny));
                    visited[nx][ny] = true;
                    map[nx][ny] = 0;                      // 해당 집을 계산했으므로 1 -> 0
                    count++;                              // 집 갯수 + 1
                }
            }
        }
    }
 
    return count;                                         // 단지 내 집의 갯수를 반환
}

 

결과

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
3
7
8
9