[백준(BOJ)] 2667번: 단지번호붙이기 (DFS/BFS, C++)

📝 문제풀이 과정

---

N x N 크기의 지도에서 집은 1로 표시된다.

대각선은 같은 단지로 취급하지 않는다. 상, 하, 좌, 우의 경우만 같은 단지이다.

출력: 단지 수, 각 단지별 집의 수를 한 줄 씩 출력한다.

current 좌표 기준 상, 하, 좌, 우를 방문하지 않았고, 좌표가 0보다 크고 N보다 작으며 (좌표에서 벗어나지 않음) 1의 값을 가지고 있으면 count++을 하고, 재귀가 끝나고 처음 호출했던 함수로 리턴하면 해당 count를 deque에 추가한다.

완료 후, result에 있는 걸 sort로 오름차순 정렬 후 출력한다.

 

 

💻 C++ 제출코드

---

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

int cnt;
int graph[25][25];
bool visited[25][25];
int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1};
void DFS(int x, int y, int N){
    cnt++;
    visited[x][y] = true;
    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(graph[nx][ny] == 1 && !visited[nx][ny]) DFS(nx, ny, N);
    }
}

int main(){ 
    int N;
    scanf("%d", &N);
    deque<int> result;

    for(int i=0; i<N; i++){
        string s; cin >> s;
        for(int j=0; j<N; j++) graph[i][j] = s[j]-'0';
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(graph[i][j] == 1 && !visited[i][j]) { 
                cnt = 0;
                DFS(i, j, N); 
                result.push_back(cnt);
            }
        }
    }
    sort(result.begin(), result.end());
    printf("%d\n", result.size());
    for(int n: result) printf("%d\n", n);
}

 

 

👏 결과

---