[백준/BOJ] 2667번: 단지 번호 붙이기 ( 깊이 우선 탐색, DFS 활용법 ) - C++ 문제 풀이

 

문제 설명

 

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

 

풀이

이 문제에서 연속되는 숫자 1들의 집합을 단지라고 합니다.

이 단지들의 숫자를 출력하고, 각 단지에 속한 숫자 1의 개수를 오름차순으로 출력하는 문제입니다.

 

먼저 입력을 받아봅시다.

#define SIZE 25
bool exist[SIZE][SIZE];

int N = 0;

cin >> N;	// 지도의 크기

string str;
for( int i = 0; i < N; i++){
    cin >> str;

    for( int j = 0; j < N; j++){

        if (str[j] == '1')	// 숫자 1이 있으면, 그 위치에 1이 있다고 표시
            exist[i][j] = true;
    }
}

정사각형의 지도에 들어있는 0과 1을 N*N 배열에 입력하는 코드입니다.

 

그다음엔, 숫자 1을 만나면 그 1과 연결되어 있는 1들을 찾는 과정입니다.

이때, 숫자 1과 인접한 1들을 탐색하는 방법으로 깊이 우선 탐색법을 사용합니다.

 

깊이 우선 탐색에 관한 내용은 여기에 있습니다.

[백준/BOJ] 24480번: 깊이 우선 탐색 2 ( DFS, Depth-First Search ) - C++ 문제 풀이

 

물론, 너비 우선 탐색을 사용할 수도 있습니다.

int cnt = 0;
vector<int> complex;	// 각 단지의 1의 개수 저장

for( int i = 0; i < N; i++){
    for( int j = 0; j < N; j++){

        if ( exist[i][j]){	// 1을 만나면 탐색 시작
            cnt = 0;
            DFS(i, j, cnt);	// 깊이 우선 탐색

            complex.push_back(cnt);	
        }
    }
}

 

깊이 우선 탐색을  코드로 작성하면 다음과 같습니다.

이때, 탐색한 위치가 다시 중복 탐색되지 않도록 1에서 0으로 변경합니다.

void DFS( int i, int j, int& cnt){

    if ( i < 0 || i >= N)	// 좌표가 지도에서 벗어나는지 확인
        return;
    if ( j < 0 || j >= N)
        return;
    if ( !exist[i][j] )	    // 1이 없는 곳은 탐색 위치가 아님
        return;

    exist[i][j] = false;    // checked
    cnt++;	    // 연속되어 있는 1의 계수 저장

    // 네 방향으로 탐색
    DFS(i-1, j, cnt);
    DFS(i+1, j, cnt);
    DFS(i, j-1, cnt);
    DFS(i, j+1, cnt);
}

 

마지막으로, 모든 단지의 개수와 각 단지의 크기를 출력하면 문제 해결입니다.

sort(complex.begin(), complex.end());   // 오름차순으로 정렬

cout << complex.size() << endl;

for( int i = 0; i < complex.size(); i++){
    cout << complex[i] << endl;
}

 

 

소스 코드

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

#define SIZE 25
bool exist[SIZE][SIZE];

int N = 0;

void DFS( int i, int j, int& cnt){

    if ( i < 0 || i >= N)
        return;
    if ( j < 0 || j >= N)
        return;
    if ( !exist[i][j] )
        return;

    exist[i][j] = false;    // checked
    cnt++;

    DFS(i-1, j, cnt);
    DFS(i+1, j, cnt);
    DFS(i, j-1, cnt);
    DFS(i, j+1, cnt);
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
        
    cin >> N;

    string str;
    for( int i = 0; i < N; i++){
        cin >> str;

        for( int j = 0; j < N; j++){

            if (str[j] == '1')
                exist[i][j] = true;
        }
    }

    int cnt = 0;
    vector<int> complex;

    for( int i = 0; i < N; i++){
        for( int j = 0; j < N; j++){

            if ( exist[i][j]){
                cnt = 0;
                DFS(i, j, cnt);

                complex.push_back(cnt);
            }
        }
    }

    sort(complex.begin(), complex.end());   // 오름차순으로 정렬

    cout << complex.size() << endl;

    for( int i = 0; i < complex.size(); i++){
        cout << complex[i] << endl;
    }

    return 0;
}