본문 바로가기

Algorithm

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

반응형

snupi.tistory.com/106

 

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

개념 트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색(search) 알고리즘이라고 한다 깊이 우선 탐색(DFS; depth-first search)은 그래프의 모든

snupi.tistory.com


다음 문제는 백준 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[] 배열을 정렬한 후에, 출력한다

반응형