[BFS] BOJ 2667 : 단지번호붙이기

 

백준 알고리즘 강의를 토대로 작성된 문제풀이입니다.
DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요.
DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)
BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)
예제 : 2019/07/22 - [프로그래밍/1일1백준] - [Graph] BOJ 1260 : DFS 와 BFS

문제

---

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

 

입력

---

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

 

출력

---

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

 

풀이

---

 

단지 ...... 

저는 제목만 보고 사진 속의 단지로 착각했는데 아니더군요....

 

 

본론으로 들어가겠습니다.

문제를 요약하자면 지도안에 몇 개의 단지가 있고 

각 단지에는 몇채의 집이 있는지를 찾는 문제입니다.

 

 

단지를 나누는 기준은 상하좌우로 이동했을 때 연결되어있지 

않은 집은 다른 단지로 구별한다고 하네요.

 

 

이 문제는 이전에 풀어본 연결요소(component) 문제와 유사합니다.

차이점은

1. 상하좌우의 이동으로 그래프를 탐색한다. (대각선을 배제하기 위해서)

2. 각 연결요소안의 정점의 수를 알아야 한다.

 

첫 번째 상하좌우로 BFS를 하는 법!

 

 

 

이건 이동을 위해 가장 기본적으로 선언되는 배열입니다.

지금까지 BFS에서 정점을 큐(queue) 에 넣었다면 지금은 좌표값을 큐에 넣습니다.

이때 x, y 좌표는 pair로 묶어 줍시다.

 

 

 

 

그리고 for 문을 통해서 상하좌우를 한 번씩 탐색하게 됩니다.

0 : 상

1 : 하

2 : 우

3 : 좌

 

그리고 좌표가 정해진 지도크기를 벗어나는 경우는 if 문을 통해

제외시켜주면 나머지는 일반적인 BFS 와 같습니다.

 

 

두 번째 각 연결 요소의 정점 수를 세는 법!

 

이건 사실 간단합니다.

우선 단지를 구별하기 위한 별도의 배열을 하나 선언합니다.

 

이 배열의 크기는 지도의 크기와 같고 집이 있는 위치에

단지의 번호가 입력됩니다.

 

 

그리고 단지 내의 집의 개수를 입력할 배열도 하나 만들어줍니다.

25 * 25 는 건물의 최대 갯수로 단지의 개수로는 절대 넘을 수 없는 크기입니다.

 

 

그러면 가볍게 2중 for 문을 통해 배열을 전부 확인해서

1이 몇개인지 ~ 

2는 몇개인지 ~ 

3은 몇개인지 ~ 

카운트만 해주면 됩니다.

 

 

나머지는 이전 문제를 보시면 전부 이해되실 거라 생각하고

문제 설명은 여기서 마치겠습니다.

 

마지막으로 이 문제에서 어려운 점 하나만 집고 넘어가겠습니다.

이 문제의 입력값은 다른 문제들과 다르게 연속된 값이 입력 됩니다.

일반적인 문제들은

 

입력 : 1 2 3 4

 

이렇게 값이 ' ' 공백을 통해서 구별이 됩니다.

하지만 이 문제는 

 

입력 : 1234

 

공백이 없기 때문에 일반적인 cin 을 통해서는 입력받는데 어려움이 있습니다.

이런 경우 문자를 하나씩 입력받는 방법이 있습니다.

 

 

이런 식으로 scanf 를 사용할 때 

"%1d" 를 사용하여 문자를 입력받게 되면

연속적인 문자가 입력돼도 하나의 문자만을 배열에 입력하게 됩니다.

 

코드

---

#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

int a[26][26];
int group[26][26];
int dx[] = { 0,0,1,-1 }; // x축 이동
int dy[] = { 1,-1,0,0 }; // y축 이동
int n;
int ans[25 * 25];

void bfs(int x, int y, int cnt) {
   queue <pair<int, int>> q; //x,y
   q.push(make_pair(x, y));
   group[x][y] = cnt;
   while (!q.empty()) {
      x = q.front().first;
      y = q.front().second;
      q.pop();
      for (int k = 0; k < 4; k++) {
         int nx = x + dx[k];
         int ny = y + dy[k];
         // 상하좌우를 한번씩 간다.
         if (0 <= nx && nx < n  && 0 <= ny && ny < n) {
            if (a[nx][ny] == 1 && group[nx][ny] == 0) {
               q.push(make_pair(nx, ny));
               group[nx][ny] = cnt;
            }
         }

      }
   }

}



int main()
{
   cin >> n;

   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         scanf("%1d", &a[i][j]);
         //붙여서 입력된 문자열을 하나씩 받기 위한 방법!!
      }
   }
   int cnt = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         if (a[i][j] == 1 && group[i][j] == 0) {
            bfs(i, j, ++cnt);
         }
      }
   }
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
            ans[group[i][j]] += 1;
      }
   }

   cout << cnt << '\n';
   sort(ans + 1, ans + cnt + 1);
   for (int i = 1; i <= cnt; i++) {
      cout << ans[i] << '\n';
   }
   return 0;
}