백준 | 2667. 단지번호 붙이기

 

1. idea - DFS로 연결된 1을 한 단지로 묶기

• 이차원 배열을 순회하면서 아직 방문 안 한 1을 찾음 → 새로운 단지 시작
• DFS/BFS로 해당 단지 전체 탐색 → 방문 표시하면서 카운트
• 단지별 집 수는 리스트(vector)에 저장

 

2 DFS 함수 만들기

• 입력된 (x, y)에서부터 시작해, 연결된 1을 모두 탐색
• 상하좌우로 움직이며, 범위를 벗어나지 않고, 1이고 방문 안 한 곳만 탐색

 

int dfs(int x, int y, int N, vector<vector<int>>& map){
    int dx[4] = {-1, 1, 0, 0}; // 왼, 오, 아래, 위
    int dy[4] = {0, 0, -1, 1}; // 왼, 오, 아래, 위

    map[x][y] = 0; // 방문처리 + 재방문 방지
    int count = 1; // 현재 집 포함해서 count 하기

    for (int i = 0; i < 4; i++) { // 방향이 4개니까 4번 반복
        int nx = x + dx[i]; // x좌표
        int ny = y + dy[i]; // y좌표

        // 범위 확인
        if (nx >= 0 && nx < N && ny >= 0 && ny < N) { //x의 범위가 제한 범위 내이고
            if (map[nx][ny]) count += dfs(nx, ny, N, map); // 반환된 집 개수에 센 집 개수 더하기
                // 집이 맞으면연결된 집 세면서 dfs계속 돌기
        }
    } //범위를 벗어나거나 더이상 집이 없으면 dfs가 끝남

    return count; // 집 개수 센거 반환
}

 

 

3. 전체 지도 순회

• map[x][y] == 1이면 새로운 단지 (visit 대신에 방문한 곳을 0으로 바꾸는 방식 적용)
• DFS 호출 → 단지 크기 리턴 → 벡터에 저장

 vector<int>cnt;
    for(int i = 0; i <N; ++i){ 
        for(int j = 0; j <N; ++j){ // vector 전체 순회
           if(map[i][j] == 1){ // 집을 만나면
                int size = dfs(i, j, N, map); // dfs실행하고, return 된 count 값을 size에 저장
                cnt.push_back(size); // vector에 단지 개수 입력
           }
        }
    }
    
    sort(cnt.begin(), cnt.end()); // 단지 내 집 개수 오름차순 정렬

    cout << cnt.size()<< endl; // 단지 개수 출력
    for(auto x : cnt) cout << x << endl; // 단지 내 집 개수 오름차순 출력

    return 0;
}

 

 

4. dfs 흐름 한 번 더 확인

dfs() 안에서 단지를 돌며 방문한 칸을 0으로 바꾸기 때문에,
이미 처리한 단지는 다시 만나도 map[i][j] == 1이 아니게 됨.

== map[i][j] == 1일 때만 dfs()를 시작하고,
그 dfs()는 연결된 모든 1들을 0으로 바꾸며 "방문 처리"를 다 해주기 때문에,
이미 속한 단지는 다시 만나도 그냥 넘어가게 되는 거!!

 

visit 함수를 만들어서 방문처리를 해도 되지만 문제가 간단하기도 하고 map 자체로 방문처리를 하는게 간단해서

나는 visit 함수 없이 map으로만 실행했음

 

5. 코드 전문

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

int dfs(int x, int y, int N, vector<vector<int>>& map){
    int dx[4] = {-1, 1, 0, 0}; 
    int dy[4] = {0, 0, -1, 1};

    map[x][y] = 0;
    int count = 1; 

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

        if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
            if (map[nx][ny] == 1) {
                count += dfs(nx, ny, N, map); 
            }
        }
    }

    return count;
}

int main(){
    int N;
    string home;
    cin >> N;

    vector<vector<int>>map(N, vector<int>(N));

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

    vector<int>cnt;
    for(int i = 0; i <N; ++i){
        for(int j = 0; j <N; ++j){
           if(map[i][j] == 1){
                int size = dfs(i, j, N, map);
                cnt.push_back(size);
           }
        }
    }
    
    sort(cnt.begin(), cnt.end());
    
    cout << cnt.size()<< endl;
    for(auto x : cnt) cout << x << endl; 

    return 0;
}