2667번 : 단지번호붙이기

Backjoon Online Judge 

"2667번 : 단지번호붙이기" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/2667

문제 및 코드 설명입니다.

'2667번 : 단지번호붙이기' 문제도 난이도가 높지 않은 문제였습니다.

BFS, DFS 어느 알고리즘으로 풀어도 상관없으며 이전 문제 해결시 BFS 많이 이용하였기에 이번에는 DFS를 적용하여 풀어 보았습니다.

먼저 지도를 저장할 배열과 방문 정보를 저장할 배열을 저장했습니다.

또 각 단지에 속하는 집의 수를 출력하기 위해 집의 수를 저장할 vector를 하나 만들었습니다.

이후 지도의 모든 점을 체크하되, 방문하지 않았고 지도의 값이 1인(집이 있는 곳)곳을 발견한다면 그 곳을 기준으로 DFS를 실행했습니다.

DFS 실행 시 단지를 체크하므로 danzi_num을 더하고 단지의 범위를 조사합니다.(상하좌우 접근을 통해)

각각의 집을 접근할 때 마다 방문 정보를 최신화하고 단지 내에서 집의 수를 저장하는 cnt값을 증가시켰습니다.

한 단지를 모두 조사하면 cnt 값을 vector에 집어넣고 cnt값은 다시 초기화 하는 방식으로 진행했습니다.

(코드를 보고 이해하는게 빠를 것이라 생각합니다.)

코드는 C++로 작성하였습니다.

(출력 시 범위기반 for문을 사용하면 (구버전)C++ 컴파일러에서 '출력초과'가 발생합니다.

C++ 17 컴파일러로 실행시 정상적으로 동작함을 확인하였고, 호환성을 위해 범위기반 for문은 주석 처리 하였습니다.)

#include <iostream>
#include <algorithm>
#include <vector>
 
#define Max 26
 
using namespace std;
 
char map[Max][Max] = { 0, };
int visit[Max][Max] = { 0, };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int N, cnt = 0;
 
void dfs(int i, int j) {
    visit[i][j] = 1;
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k];
        int y = j + dy[k];
        if (0 <= x && x < N && 0 <= y && y < N) {
            if (map[x][y] == '1' && !visit[x][y]) {
                cnt++;
                dfs(x, y);
            }
        }
    }
}
 
int main() {
    int danzi_num = 0;
    vector<int> house_num;
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> map[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == '1' && !visit[i][j]) {
                danzi_num++;
                cnt = 1;
                dfs(i, j);
                house_num.push_back(cnt);
            }                
        }
    }
    sort(house_num.begin(), house_num.end());
 
    cout << danzi_num << endl;
    
    /* (범위기반 for문 : 구버전 컴파일러에서 '출력 초과'가 나타남)
    for (int i: house_num) {
        cout << i << endl;
    } */
 
    for (int i = 0; i < house_num.size(); i++) {
        cout << house_num[i] << endl;
    }
}