[백준/BOJ] 11725번: 트리의 부모 찾기 ( 깊이 우선 탐색 ) - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 트리를 구성하는 각 노드의 부모 노드 번호를 출력하는 문제입니다.

 

먼저, 입력된 데이터로부터 트리를 구성하고, 루트(root)인 1번 노드부터 연결되어 있는 노드들을 탐색해서, 부모 노드를 기록했다가 출력하면 될 것입니다.

주어진 데이터가 트리라고 했으므로, 분리된 노드는 고려하지 않아도 됩니다.

 

이 문제에선, 깊이 우선 탐색( DFS ) 방법을 사용했습니다.

 

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

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

 

아래의 코드는 트리를 구성하는 코드입니다.

#define SIZE   100000	// 노드 개수

vector<int> T[SIZE+1];	// 한 노드에 연결되어 있는 노드들의 백터 배열

int N = readInt();

int a, b;
for(int i = 0; i < N-1; i++){
	a = readInt();
	b = readInt();

	T[a].push_back(b);	// a,b가 연결되어 있음을 기록
	T[b].push_back(a);
}

 

그다음, 깊이 우선 탐색을 합니다.

1번 노드가 root라고 했으므로 1번 노드부터 탐색을 시작합니다.

void DFS( int vert, int parent){	// 깊이 우선 탐색

    P[vert] = parent;	// 노드의 부모 노드 기록

    for( int x : T[vert]){

        if ( P[x] == 0){
            DFS( x, vert);
        }
    }
}

 

 

소스 코드

#include <iostream>
#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 SIZE   100000

int P[SIZE+1];  // save parent node

vector<int> T[SIZE+1];

void DFS( int vert, int parent){

    P[vert] = parent;

    for( int x : T[vert]){

        if ( P[x] == 0){
            DFS( x, vert);
        }
    }
}

int main(){

    int N = readInt();
    
    int a, b;
    for(int i = 0; i < N-1; i++){
        a = readInt();
        b = readInt();

        T[a].push_back(b);
        T[b].push_back(a);
    }

    DFS(1, 1);

    for(int i = 2; i <= N; i++){
        writeInt(P[i]);
    }

    wbflush();

    return 0;
}