(매일 BOJ) C++ 2667번 단지번호붙이기

이번 문제는 2667번 단지번호붙이기 문제다

문제 개요

문제 : 백준 2667번

 

0과 1로 이루어진 N×N 크기의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳
서로 인접한 집들이 모여 하나의 단지를 형성하며, 인접은 상하좌우로만 판정

 

목표

• 단지의 개수 출력
• 각 단지에 속하는 집의 수를 오름차순으로 출력

접근법

이 문제는 그래프 탐색 문제로, 2D 격자를 그래프로 보고 DFS(깊이 우선 탐색)로 해결하였다

1. 전체 지도(map)를 입력받아 저장.
2. 방문 여부를 체크할 visited 배열 준비.
3. 모든 좌표를 순회하며:
   • 방문하지 않았고 집(1)이 있다면 DFS 시작.
   • DFS로 연결된 모든 집을 방문 처리하고 개수를 센 뒤 리스트에 저장.
4. 단지 개수 출력 후, 각 단지의 집 수를 오름차순으로 출력.

작성코드

#include <bits/stdc++.h>
using namespace std;

void DFS (vector<vector<int>> &,vector<vector<bool>> &,int i,int j, int&);
int fourways_x[4] = {0,0,1,-1};
int fourways_y[4] = {1,-1,0,0};
int N;

int main (void){
    
    cin >> N;
    vector<vector<int>> map(N,vector<int>(N)); 
    for(int i = 0; i < N; i++){
        string str;
        cin >> str;
        int cnt = 0;
        for(char s : str){
            map[i][cnt] = s - '0';
            cnt += 1;
        }
    }

    vector<vector<bool>> visited (N,vector<bool>(N,false));
    int cnt_connectedparts = 0, cnt_parts = 0;
    vector<int> parts_num;


    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if (!visited[i][j] && map[i][j] == 1){
                cnt_parts = 1;
                DFS(map,visited,i,j,cnt_parts);
                parts_num.push_back(cnt_parts);
                cnt_connectedparts += 1;
            }
        }
    }
    cout << cnt_connectedparts << '\n';

    sort(parts_num.begin(),parts_num.end());

    for(auto a : parts_num){
        cout << a << '\n';
    }

    return 0;
}

void DFS (vector<vector<int>> & map,vector<vector<bool>> & visited,int i,int j, int& cnt_parts){
    visited[i][j] = true;

    int next_x,next_y;
    for(int o = 0; o < 4; o++){
        next_x = i + fourways_x[o];
        next_y = j + fourways_y[o];

        if(next_x >= 0 && next_y >= 0 && next_x < N && next_y < N && visited[next_x][next_y] == false && map[next_x][next_y] == 1){
            cnt_parts += 1;
            DFS(map,visited,next_x,next_y,cnt_parts);
        }
    }
}

시간 복잡도

• DFS 한 번으로 연결된 집 전체를 방문하므로, 모든 칸을 최대 한 번만 방문 → O(N²)