BOJ 2667 - 단지 번호 붙이기 / C++

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

2667번: 단지번호붙이기

 

 

문제 풀이

지도를 입력받아 순차적으로 돌며 집이 있고 방문하지 않은 곳을 발견하면 해당 지점부터 DFS 또는 BFS를 시작하여 연결되어 있는 집을 모두 찾아 단지 수를 증가시켜주면 된다. 이러한 방식으로 모두 체크한 뒤, 단지 수와 각 단지에 속한 집의 수를 오름차순으로 출력하면 된다.

 

소스 코드

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

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int n, house = 0, complex = 0;
bool visited[26][26] = { false, };
int map[26][26];
vector<int> houses;

void DFS(int y, int x){
    visited[y][x] = true;
    house++;

    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || ny < 0 || nx >= n || ny >= n){
            continue;
        }
        
        if(map[ny][nx] == 1 && visited[ny][nx] == false){
            DFS(ny, nx);
        }
    }
}

int main(){
    cin >> n;

    for(int i=0; i<n; i++){
        string tmp;
        cin >> tmp;
        for(int j=0; j<n; j++){
            map[i][j] = tmp[j] - '0';
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(map[i][j] == 1 && visited[i][j] == false){
                DFS(i, j);
                complex++;
                houses.push_back(house);
                house=0;
            }
        }
    }
    sort(houses.begin(), houses.end());

    cout << houses.size() << '\n';

    for(int i=0; i<houses.size(); i++){
        cout << houses[i] << '\n';
    }
}

 

DFS 함수를 보게 되면 일반적으로 아는 x, y순서가 아니라 바뀌어 있는 것을 볼 수 있다.

2차원 배열을 생각할 때 아래와 같이 떠올리는데 이 때, 오른쪽으로 가려면 열의 좌표가 바뀌기 때문에 열 이동은 x좌표, 행 이동은 y 좌표를 사용하는 것을 알 수 있다. 따라서 map[y][x]와 같이 표현된다.