BOJ 2667 - 단지번호 붙이기

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

2667번: 단지번호붙이기

 

DFS 를 이용해서 

주어진 인접 행렬에서 구분된 구역의 갯수와 구역 내의 원소의 총 갯수를 구하는 문제이다.

 

DFS 에 대한 기본적인 개념을 다지기 좋은 문제이다.

 

 

- c++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, cnt;                // 총 노드의 수 (5 ~ 25), 갯수 출력 변수
int checked[25][25];       // 방문 여부를 나타내는 배열
int dx[4] = {0, 1, 0, -1}; 
int dy[4] = {-1, 0, 1, 0}; 
string adj[25];            // 인접노드를 나타내는 배열
vector<int> answer;        // 답안 출력을 위한 변수
 
void DFS(int i, int j)
{
    checked[i][j] = true;
    cnt++;
 
    for (int k = 0; k < 4; k++)
    {
        int newX = i + dx[k];
        int newY = j + dy[k];
 
        if ((0 <= newX && newX < n) && (0 <= newY && newY < n))
        {
            if (adj[newX][newY] == '1' && !checked[newX][newY])
            {
                DFS(newX, newY);
            }
        }
    }
}
 
int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin >> n; // 지도의 크기 n 을 입력
    for (int i = 0; i < n; i++)
    {
        cin >> adj[i];
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (adj[i][j] == '1' && !checked[i][j])
            {
                // 행렬의 해당 번지수의 값이 1 이면서, 방문하지 않은 경우
                cnt = 0;
                DFS(i, j);
                answer.push_back(cnt);
            }
        }
    }
 
    cout << answer.size() << '\n'; // answer 의 size 가 총 단지수(구분된 구역의 수)를 의미한다.
    sort(answer.begin(), answer.end());
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << '\n'; // answer 각각의 원소 값이 단지 내의 주거지 수를 의미한다.
    }
    return 0;
}