[C++] 백준11725 : 트리의 부모찾기

문제 설명

 

1. 입력으로 연결된 트리 정보를 알려준다.

2. 이 트리의 모든 노드의 부모 노드가 몇번인지를, 순서대로 출력해라

 

 

문제 풀이

 

1. 처음에는 노드의 연결정보를 2차원 배열로 표현하려 했다, 하지만 N이 100000이여서 시간복잡도가 매우 불리해지는걸 알고 고민에 빠졌다.

2. 이진트리에 관한 정보를 찾아보다가, 인접리스트로 구현을 하면 된다는 사실을 깨달았다.

3. bfs분류로 들어가서 문제를 풀었지만, dfs로도 풀 수 있음을 알게되었다. 부모-자식 노드를 순서대로 흝고가는 탐색법이기 때문이다.

4. dfs를 재귀 호출시에, visited를 다시 false로 고쳐주는 코드가 필요 없음을 깨달았다. 모든 dfs의 경우의수를 찾는것이 아닌 단 한번만 node들을 흝으면 되기 때문이다.

5. 결론적으로, dfs로 모든 노드들을 한번씩 검사하면서, answer 리스트에 부모 노드가 몇번인지를 기록해주면 된다.

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

int N;
vector<vector<int>> G(100001, vector<int>{}); // 인접 리스트
bool visited[100001]; // 방문여부체크
int answer[100001]; // 정답 배열

void dfs(int parent) {
	visited[parent] = true;

	for (int i = 0; i < G[parent].size() ; i++) {
		int child = G[parent][i];
		if (!visited[child]) {	
			answer[child] = parent;
			dfs(child);
		}
	}	
}

int main() {
	cin >> N;

	//인접 리스트
	int a, b;
	for (int i = 0; i < N-1; i++) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	// dfs 시작
	dfs(1);

	for (int i = 2; i<N+1; i++) {
		cout << answer[i] << '\n';
	}
}