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

문제

[C++] 백준 11725: 트리의 부모 찾기 SILVER 2
https://www.acmicpc.net/problem/11725

 

---

 

접근 방법

이 문제는 루트가 1번인 트리가 주어졌을 때, 각 노드의 부모를 출력하는 문제다.

 

트리는 사이클이 없는 연결 그래프이기 때문에,
1번 노드를 기준으로 DFS를 한 번만 돌면서 부모를 기록해주면 해결된다.

 

구현 아이디어는 간단하다:

• graph : 인접 리스트 (양방향 그래프)
• ret[i] : i번 노드의 부모 노드 번호
• visited[i] : 방문 체크

DFS에서

void dfs(int before, int now)
{
    visited[now] = true;
    ret[now] = before; // now의 부모는 before

    for (int i = 0; i < graph[now].size(); i++)
    {
        int next = graph[now][i];

        if (!visited[next])
            dfs(now, next);  // 현재 노드(now)를 다음 노드(next)의 부모로 넘김
    }
}

이렇게 현재 노드의 부모를 before 파라미터로 받도록 해서, 재귀 호출을 할 때마다 자연스럽게 부모–자식 관계를 채운다.

루트 노드인 1번에서 시작할 때는 부모가 없으므로 dfs(0, 1); 처럼 0을 넘겨서 시작한다. (0은 단순한 더미 값)

 

DFS가 끝난 뒤에는

for (int i = 2; i <= n; i++)
    cout << ret[i] << '\n';

2번 노드부터 N번 노드까지의 부모만 출력하면 된다.
(1번은 루트라 부모가 없음)

 

구현 시 주의할 점

• 트리 입력은 간선이 양방향으로 주어지므로 양쪽 모두에 넣어줘야 한다.

graph[index].push_back(val);
graph[val].push_back(index);

 

• DFS에서 부모를 찾을 때, 바로 이전 노드만 부모라고 단정할 수 없으므로 visited 배열로 이미 방문한 노드를 다시 타고 들어가지 않게 해야 한다.
  그렇지 않으면 부모–자식 관계가 꼬이거나 무한 재귀가 발생할 수 있다.
• 인덱스는 1부터 N까지 사용하므로, graph, visited, ret는 모두 n + 1 크기로 잡는 것이 안전하다.
• 루트(1번 노드)의 부모는 의미가 없으니 출력에서 제외하고, 2번 노드부터 출력해야 한다는 점을 잊지 말기.

 

 

---

 

코드

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

vector<vector<int>> graph;
vector<int> ret;
vector<bool> visited;
int n;

void dfs(int before, int now)
{
	visited[now] = true;
	ret[now] = before;

	for (int i = 0; i < graph[now].size(); i++)
	{
		int next = graph[now][i];

		if (!visited[next])
			dfs(now, next);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	graph.resize(n + 1);
	visited.resize(n + 1, false);
	ret.resize(n + 1, 0);
	for (int i = 1; i < n; i++)
	{
		int index = 0, val = 0;
		cin >> index >> val;

		graph[index].push_back(val);
		graph[val].push_back(index);
	}
	dfs(0, 1);

	for (int i = 2; i <= n; i++)
		cout << ret[i] << '\n';
}