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

 

문제 설명

 

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

 

풀이

이 문제는 각 정점을 방문하는 순서를 출력하는 문제입니다.

정점을 방문하는 방식은 깊이 우선 탐색( Depth-first Search, DFS )을 따릅니다.

 

깊이 우선 탐색은 이웃하는 노드가 아니라 자식 노드를 먼저 탐색하는 방식입니다.

이미지를 보면서 설명을 읽는 것이 쉽게 이해할 수 있을 것 같습니다.

 

깊이 우선 탐색 과정

 

위의 이미지에서 탐색 경로는 다음과 같습니다.

먼저 루트(root)인 1부터 탐색을 시작해서, 자식 노드인 2를 탐색합니다.

그다음은 이웃 노드인 3이 아니라, 2의 자식 노드인 3을 탐색하고, 차례로 자식 노드인 4, 8까지 "자신 노드 우선"으로 탐색을 합니다.

그리고, 그다음은 8 노드에서 한 단계 올라가, 4 노드의 자식인 9 노드를 탐색합니다.

 

이러한 방식으로 모든 노드(정점)를 탐색하는 방법이 깊이 우선 탐색입니다.

 

이 문제는 깊이 우선 탐색의 방식을 알 수 있도록 구성된 문제입니다.

따라서, 정점과 간선을 표현하는 데이터를 어떻게 다룰 것인가를 결정하고 나면,

나머지는 문제 설명을 따라 구현만 하면 되겠습니다.

 

간선(edge)은 두 개의 정점(vertex)으로 표현됩니다.

그래서, 정점 v에 여러 개의 간선이 있는 경우 (v-v1), (v-v2), (v-v3)... 등으로 표현됩니다.

이 데이터들을 한 번에 담기 위해서 vector를 이용했습니다.

#define VERTEX_SIZE 100000

typedef int MTYPE;

vector<MTYPE> vert[VERTEX_SIZE+1];	// 모든 edge 정보를 담고 있는 vertex 배열

예를 들어, 정점 1에 이어진 간선들의 정보는 vert [1] 벡터에 저장한, 대응되는 정점의 숫자들로 표현할 수 있습니다.

(1-vert [1][0]), (1-vert [1][1]), (1-vert [1][2])... 등등

 

문제에서 입력된 간선 정보를 위의 구조에 입력합니다.

for( int i = 0; i < M; i++){	//  간선의 개수

    A = readInt();		// 간선을 표현하는 정점 2개
    B = readInt();

    vert[A].push_back(B);	// A 정점에 이어져 있는 간선 정보
    vert[B].push_back(A);	
}

 

이제, 깊이 우선 탐색을 구현하면 다음과 같습니다.

int visited[VERTEX_SIZE+1];	// 몇 번째에 방문한 정점인지를 기록

int cnt = 1;    // visited vertex count

void DFS( MTYPE R ){	// R은 방문한 정점
    
    visited[R] = cnt++; // 방문 순서 ( R vertex가 몇 번째 방문되는가 )
    
    // 정점 R과 연결된 정점들을 내림차순으로 정렬
    sort( vert[R].begin(), vert[R].end(), greater<MTYPE>());

    // 정점 R와 이어져 있는 정점 탐색
    for( MTYPE x : vert[R]){
        
        if ( !visited[x]){
            DFS(x);
        }
    }
}

정점 R과 이어져 있는 정점을 탐색하기 위해 vert [R] 벡터에 담겨있는 간선 정보를 순환하는 코드입니다.

 

참고로, vector의 멤버를 순환하기 위해서 범위 기반 for 구문을 사용했습니다.

범위 기반 for 구문에 대한 내용은 여기에 정리해 두었습니다.

[C++] 범위 기반 for 루프 (Range-based for loop) 사용법

 

이 함수는 재귀적으로 호출을 하기 때문에, 먼저 R과 이어져 있는 첫 번째 정점을 따라 도달할 수 있는 정점까지 탐색을 마친 후, 두 번째 이어져 있는 정점을 탐색하는 순서로 진행됩니다.

이와 같이, 깊이 우선 탐색은 재귀적 함수 호출을 특징으로 합니다.

 

마지막으로, 모든 정점의 방문된 순서를 출력하면 문제 해결입니다.

for( int i = 1; i <= N; i++){	// N은 정점의 개수
    writeInt( visited[i]);
}

 

참고로, 데이터를 입력받는데 cin 객체를 사용하면 시간제한에 걸리기 때문에

한 번에 데이터를 읽어오는 방식을 사용했습니다.

 

소스 코드

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

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
char wbuf[WBUF_SIZE];
int widx, ridx, nidx;

inline char read() {
	if (ridx == nidx) {
		nidx = fread(rbuf, 1, 1 << 20, stdin);
		if (!nidx) return 0;
		ridx = 0;
	}
	return rbuf[ridx++];
}
inline int readInt() {
	int sum = 0;
	char now = read();
	bool flg = false;

	while (now <= 32) now = read();
	if (now == '-') flg = true, now = read();
	while (now >= 48) sum = sum * 10 + now - '0', now = read();

	return flg ? -sum : sum;
}
int unitSize(int n) { // 자리 수
	if (n < 0)n = -n;
	int ret = 1;
	while (n >= 10) {
		ret++;
		n /= 10;
	}
	return ret;
}
void wbflush() {
	fwrite(wbuf, 1, widx, stdout);
	widx = 0;
}
void write(char c) {
	if (widx == WBUF_SIZE) wbflush();
	wbuf[widx++] = c; 
}
void writeInt(int n) {
	int isz = unitSize(n);
	if (isz + widx >= WBUF_SIZE) wbflush();

	if (n < 0) {
		wbuf[widx++] = '-';
		n = -n;
	}

	int next = widx + isz;
	while (isz--) {
		wbuf[widx + isz] = n % 10 + '0';
		n /= 10;
	}
	widx = next;
	write('\n'); // 구분자
}

//----------------------------------------------------------

#define VERTEX_SIZE 100000

typedef int MTYPE;

vector<MTYPE> vert[VERTEX_SIZE+1];
int visited[VERTEX_SIZE+1];

int cnt = 1;    // visited vertex count

void DFS( MTYPE R ){
    
    visited[R] = cnt++; // 방문 순서 ( R vertex가 몇 번째 방문되는가 )
    
    sort( vert[R].begin(), vert[R].end(), greater<MTYPE>());

    for( MTYPE x : vert[R]){
        if ( !visited[x]){
            DFS(x);
        }
    }
}

int main(){

    int N, M, R;    // vertex 개수, edge 개수, 시작 vertex
    MTYPE A, B;     // edge 정보

    N = readInt();
    M = readInt();
    R = readInt();

    for( int i = 0; i < M; i++){

        A = readInt();
        B = readInt();

        vert[A].push_back(B);
        vert[B].push_back(A);
    }

    DFS(R);

    for( int i = 1; i <= N; i++){
        writeInt( visited[i]);
    }

    wbflush();
   
    return 0;
}