[백준 2667번][C] 단지번호붙이기 (DFS)

snupi.tistory.com/106

[C] 깊이 우선 탐색(DFS; Depth First Search) 개념 및 정리

---

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

 

출처 : https://www.acmicpc.net/problem/2667

전형적인 DFS 또는 BFS 그래프 경로 순회 문제이다

 

• 배열의 인접한 부분을 탐색하며 단지 수를 카운팅한다
• 더불어 나눠진 컴포넌트가 있는 그래프이므로 몇 개의 컴포넌트인지 파악까지 해야 한다
• 마지막으로, 단지 수를 오름차순으로 출력한다

---

0. 전역 변수 설정

#include<stdio.h>
#define MAX 26 // 최대 25 인덱스까지 사용

int adj[MAX][MAX]; // 인접행렬 자료 만들 때 사용
int visited[MAX][MAX]; // 방문했는지 check
int cntIdx; // 컴포넌스 수
int cnt[MAX*MAX/2]; // 각 컴포넌스의 단지 수

 

1. 지도의 크기와 자료 입력

// 지도의 크기 입력
scanf("%d", &N);
// 지도를 전체 돌며 자료 입력
for(int i=1; i<=N; i++) {
    for(int j=1; j<=N; j++) {
        // %1d 로 숫자 하나씩 입력
        scanf("%1d", &adj[i][j]);
        // adj가 0일 경우, 방문 check를 하여 순회하지 않도록 한다
        if(adj[i][j] == 0)
            visited[i][j] = 1;
    }
}

 

2. DFS 순회

void DFS(int hereY, int hereX, int N) { // 정점과 정점개수
    int thereY, thereX;
    visited[hereY][hereX] = 1; // 방문 check
    cnt[cntIdx-1]++; // 컴포넌트의 단지 수 증가

    // 인접 확인하기 (상하좌우 4가지)
    if(adj[hereY-1][hereX] == 1) {
        // there 설정
        thereY = hereY-1;
        thereX = hereX;
        // visited 확인하고 재귀
        if(!visited[thereY][thereX]) {
            DFS(thereY, thereX, N); //발견하자마자 바로 함수로 다시 들어가
        }
    }
    if(adj[hereY+1][hereX] == 1) {
        // there 설정
        thereY = hereY+1;
        thereX = hereX;
        // visited 확인하고 재귀
        if(!visited[thereY][thereX]) {
            DFS(thereY, thereX, N); //발견하자마자 바로 함수로 다시 들어가
        }
    }
    if(adj[hereY][hereX-1] == 1) {
        // there 설정
        thereY = hereY;
        thereX = hereX-1;
        // visited 확인하고 재귀
        if(!visited[thereY][thereX]) {
            DFS(thereY, thereX, N); //발견하자마자 바로 함수로 다시 들어가
        }
    }
    if(adj[hereY][hereX+1] == 1) {
        // there 설정
        thereY = hereY;
        thereX = hereX+1;
        // visited 확인하고 재귀
        if(!visited[thereY][thereX]) {
            DFS(thereY, thereX, N); //발견하자마자 바로 함수로 다시 들어가
        }
    }    
}

// 나눠진 컴포넌트는 DFS()로 순회하지 못하므로, 행력 전체를 확인한다
void DFSAll(int N) {
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            if(!visited[i][j]) {
                // 컴포넌트 수 증가
                cntIdx++;
                DFS(i, j, N);
            }
        }
    }
}

 

3. cntIdx 만큼의 cnt[] 배열을 정렬한 후에, 출력한다