[백준] 2667.cpp : 단지번호붙이기

www.acmicpc.net/problem/2667 

2667번: 단지번호붙이기

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

int n;
char map[25][25];                       // 지도 정보
int dir[4] = {1, -1, 0, 0};             // 상하좌우 방향 깔끔하게

int dfs(int row, int col)
{
    if(map[row][col] == '0') return 0;  // 빈 곳은 그냥 종료
    if(row < 0 || row >= n || col < 0 || col >= n) return 0; // 이외에도 인덱스 초과 시 그냥 종료

    map[row][col] = '0';                // 해당 집을 방문했다고 표시
    int ret = 1;                        // 집의 수 1
    for(int i = 0 ; i < 4 ; i++)
    {
        ret += dfs(row + dir[i], col + dir[3 - i]); // 같은 단지에 속한 집들을 재귀적으로 검사하여
    }
    return ret;                         // 단지에 속한 전체 집의 수를 반환
}

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n;
    for(int r = 0 ; r < n ; r++)
    {
        for(int c = 0 ; c < n ; c++)
        {
            cin >> map[r][c];
        }
    }
    int ans = 0;                                    // 단지의 수
    vector<int> numbers;                            // 단지별로 속한 집의 수
    for(int r = 0 ; r < n ; r++)
    {
        for(int c = 0 ; c < n ; c++)
        {
            if(map[r][c] != '0')                    // 만약 검사하지 않은 단지가 있다면
            {
                int temp = dfs(r, c);               // 단지를 싹 검사해주고
                numbers.push_back(temp);            // 단지에 속한 집의 수를 넣어주고
                ans++;                              // 단지의 수 증가
            }
        }
    }
    sort(numbers.begin(), numbers.end());           // 단지별 집의 수 정렬 후 
    cout << ans << '\n';        
    for(int i = 0 ; i < numbers.size() ; i++)       // 오름차순 출력
    {
        cout << numbers[i] << '\n';
    }
}

 

[Approach]

1. 알고랩에서 풀었던 방의크기구하기와 같이 DFS 활용해서 풀면 간단할 것 같다.

 

[Point]

1. BFS 로 큐 사용해서 풀었으면 각 단지에 속하는 집의 수를 더 쉽게 구했을 것 같은데, DFS 가 나는 더 편한 것 같다.

2. 그런데 다들 DFS 로 풀었네... 태그는 왜 너비우선탐색으로 되어있는거지

3. 집의 수를 구할 때도 굳이 반환형을 int 로 하지 않고 해당 값에 대한 배열을 전역 변수로 놨다면 더 편하게 짰을 것 같다.