[Boj] 백준 C++ #2667 단지번호붙이기

📍알고리즘 분류: DFS, BFS
DFS란 Depth First Search, 깊이 우선 탐색. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 재귀호출이나 스택 배열로 구현할 수 있다.

📍문제풀이: 재귀호출 방식의 DFS로 문제를 풀었다. dfs가 처음 호출되면 인접한 집들을 다 탐색하여 한 단지를 구성하는 집의 개수를 모두 센다.

📍코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX_N 26
int map[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1}; //좌 우 상 하
int cnt;
int N;

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

        if(nx>=N||nx<0||ny>=N||ny<0) continue;

        if(!visited[nx][ny] && map[nx][ny]){ //방문하지 않은 집이면
            visited[nx][ny] = 1; //방문했다고 표시
            cnt++; //단지내 집 개수
            dfs(nx,ny); //dfs 재귀 호출
        }
    }
}

int main() {
    vector<int> complex_cnt;
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    vector<int> complex_sizes; //단지 수를 저장할 벡터
    memset(visited,0,sizeof(visited)); //visited 벡터 초기화

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(!visited[i][j]&&map[i][j]){ //방문하지 않은 집이면
                visited[i][j] = 1; //방문 표시
                cnt++;
                dfs(i,j);
                complex_cnt.push_back(cnt);
                cnt = 0; //집 개수 초기화
            }
        }
    }
    int complex_cnt_size = complex_cnt.size();
    sort(complex_cnt.begin(), complex_cnt.end());
    cout<<complex_cnt_size<<endl; // 단지 개수 출력
    for(int i=0;i<complex_cnt_size;i++){
        cout<<complex_cnt[i]<<endl; //단지 내 집 개수 출력
    }
    return 0;
}

 

많이 참고한 블로그!

https://nanyoungkim.tistory.com/62