[BOJ] #2667 단지번호붙이기

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

2667번: 단지번호붙이기

---

BFS 문제를 계속 풀어보고 있는데, 이 문제 또한 비슷한 형태의 알고리즘이다. BFS로 풀리는 문제는 정해진 몇몇개의 특징이 있는 듯 하다.

1. 가중치가 없는 그래프에서 최단 경로를 찾아야 한다거나
2. 그런 최단 경로의 갯수를 구한다거나
3. 어떤 행렬이나 지도를 주고 그 지도에서 같은 부분으로 묶이는 영역을 구한다거나

이런 특정한 조건이 들어간 문제가 있으면 웬만하면 BFS로 접근해라 라는 의미인거 같다.

이 문제 또한 그렇다. "지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램"을 작성하는 문제이다. pair형 큐 자료구조를 선언해준 뒤에, 그를 이용하여 BFS 방식으로 해결했다. 이때 신경써야 할 점은 주어진 지도 배열에서 상하좌우를 탐색하며 인접한 유효한 값이 있는지 검사하는 부분인데, 조건문 4개를 연달아 써서 작성해도 되겠지만..

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };

따로 이렇게 배열을 선언해준 뒤, 

for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if (newX >= 0 && newX < N && newY >= 0 && newY < N && visited[newX][newY] == false && arr[newX][newY] == 1) {
                Q.push(make_pair(newX, newY));
                visited[newX][newY] = true;
                cnt++;
            }
        }

이런 식으로 그냥 반복문 안에 한번에 넣어서 좌표연산을 해주면, 보다 수월하게 좌표에 접근하여 구현해줄 수 있다. 이번 문제와 비슷한 유형에서 자주 써먹을만한 것이다 보니 잘 숙지해두자.

 

그리고 "각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오." 라는 조건이 있는데, 이건 그냥 vector에 싸그리 넣어준 후, sort를 이용하여 오름차순 정렬을 해주었다.

처음에 문제를 어떻게 풀지 구상할때에, 인접한 무리들이 있으면 어떻게 그들을 한데 묶어서 처리할까 생각도 했는데, 애초에 그럴 필요도 없는게 BFS 알고리즘 과정에서 이미 한번 방문한 정점을 visited에 따로 저장해두고 탐색에 활용하기 때문에 어차피 한번 방문한 정점은 다시 한번 방문하지 않는다. 따라서 그것들을 한데 묶을 필요도 없고, 그냥 인접한 정점끼리 묶인 집합들만 신경쓰면 되는것이다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX 26

using namespace std;

int N;
int arr[MAX][MAX];
bool visited[MAX][MAX] = { false };
vector<int> V;

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };
            //상  하  좌  우 

void BFS(int x, int y) {
    queue<pair<int,int>> Q;
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    int cnt = 0;
    cnt++;

    while(!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if (newX >= 0 && newX < N && newY >= 0 && newY < N && visited[newX][newY] == false && arr[newX][newY] == 1) {
                Q.push(make_pair(newX, newY));
                visited[newX][newY] = true;
                cnt++;
            }
        }
    }
    V.push_back(cnt);
}

int main () {
    cin >> N;

    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            scanf("%1d", &arr[i][j]);

    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            if (visited[i][j] == false && arr[i][j] == 1) BFS(i,j);

    sort(V.begin(), V.end());
    cout << V.size() << '\n';
    for (int idx : V) cout << idx << '\n';

    return 0;
}