[백준/BOJ] 24445번: 너비 우선 탐색 2 ( BFS, Breath-First Search ) - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 각 정점을 방문하는 순서를 출력하는 문제입니다.
정점을 방문하는 방식은 너비 우선 탐색( Breath-first Search, BFS )을 따릅니다.

 

너비 우선 탐색은 자식 노드가 아니라 이웃하는 노드를 먼저 탐색하는 방식입니다.
이미지를 보면서 설명을 읽는 것이 쉽게 이해할 수 있을 것 같습니다.

 

 

너비 우선 탐색 ( BFS ) 순서

 

위의 이미지에서 탐색 경로는 다음과 같습니다.
먼저 루트(root)인 1부터 탐색을 시작해서, 자식 노드인 2를 탐색합니다.
그다음은 2의 자식 노드인 4를 탐색하는 것이 아니라, 이웃 노드인 3을 탐색합니다.

그리고, 그다음은 2 레벨 탐색으로, 2의 자식 노드인 4, 5를 탐색하고, 

3의 자식 노드이자, 5 노드의 이웃 노드인 6, 7을 탐색합니다.

 

이렇게 "이웃 노드 우선"으로 모든 노드(정점)를 탐색하는 방법이 너비 우선 탐색입니다.

 

이 문제는 너비 우선 탐색의 방식을 알 수 있도록 구성된 문제입니다.
따라서, 정점과 간선을 표현하는 데이터를 어떻게 다룰 것인가를 결정하고 나면,
나머지는 문제 설명을 따라 구현만 하면 되겠습니다.

 

간선(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);	
}

 

이제, 너비 우선 탐색을 구현하면 아래 코드와 같습니다.

문제에서는 큐(queue)를 사용해서, 탐색해야 할 정점을 차례로 저장하고 있습니다.

 

큐에 관한 내용은 여기에 정리해 두었습니다.

[백준/BOJ] 18258번: 큐 2 ( Queue 자료 구조 사용하기 ) - C++ 문제 풀이

 

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

int cnt = 1;    		// visited vertex count

void BFS( MTYPE R ){		// R은 방문한 정점
    
    visited[R] = cnt++; 	// 방문 순서 ( R vertex가 몇 번째 방문되는가 )
    
    queue<MTYPE> qu;
    qu.push(R);

    while( !qu.empty()){

        MTYPE v = qu.front();
        qu.pop();

	// 정점 v과 연결된 정점들을 내림차순으로 정렬
        sort( vert[v].begin(), vert[v].end(), greater<MTYPE>());

	// 정점 v와 이어져 있는 정점 탐색
        for( MTYPE x : vert[v]){
            if (!visited[x]){
                visited[x] = cnt++;	// 탐색되었음. 방문한 순서를 기록
                qu.push(x);		// 다음에 탐색할 노드 저장
            }
        }
    }
}

정점 R을 시작으로 하여, R과 이어져 있는 정점들을 먼저 탐색하고, 탐색한 정점 x를 큐(queue)에 담아서,

다음 순환 시에 정점 x와 이어져 있는 정점들을 탐색하는 코드입니다.

 

참고로, 정점 v에 연결된 정점 vector의 멤버를 순환하기 위해서 범위 기반 for 구문을 사용했습니다.
범위 기반 for 구문에 대한 내용은 여기에 정리해 두었습니다.

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

 

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

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

 

데이터를 입력받는데 cin 객체를 사용하면 시간제한에 걸리기 때문에
한 번에 데이터를 읽어오는 방식을 사용했습니다.

 

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
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 BFS( MTYPE R ){
    
    visited[R] = cnt++; // 방문 순서 ( R vertex가 몇 번째 방문되는가 )
    
    queue<MTYPE> qu;
    qu.push(R);

    while( !qu.empty()){

        MTYPE v = qu.front();
        qu.pop();

        sort( vert[v].begin(), vert[v].end(), greater<MTYPE>());

        for( MTYPE x : vert[v]){
            if (!visited[x]){
                visited[x] = cnt++;
                qu.push(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);
    }

    BFS(R);

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

    wbflush();
   
    return 0;
}