[백준11725]| 트리의 부모찾기

문제 :

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제입력:

7
1 6
6 3
3 5
4 1
2 4
4 7

예제출력:

4
6
1
3
1
4

---

방법론:

1) 트리 그래프를 만든다
2) 각 노드의 부모노드를 구한다

트리그래프 만들기

1) 먼저 빈 템플릿 그래프를 만든다

graph = [[]for _ in range(N+1)]

그럼 다음과 같은 그래프가 완성된다.
여기서는 0번 노드가 존재하지 않기 때문에 0번은 사용하지 않는 노드라고 생각하면 되고, 각 노드 안에는 이웃하는 노드 즉 parent node와 child 노드가 담긴다.

graph = [
[], # 0번 노드
[], # 1번 노드
[], # 2번 노드
[], # 3번 노드
[], # 4번 노드
[], # 5번 노드
[], # 6번 노드
[], # 7번 노드
]

2) 둘째 줄부터 입력된 두 정점으로 graph를 완성해보자

for _ in (N-1): #N-1개 줄에 입력된다고 했으니 N-1번 진행
	a,b = map(int, input().split()) # a랑 b 추출
    graph[a].append(b)
    graph[b].append(a)

결과값은 다음과 같다

[[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]]

DFS (Depth First Search)로 결과 탐색

1) 부모값을 저장해두는 리스트를 만든다 parent=[0]*(N+1)
2) 1번 노드의 부모는 1이라고 임의로 둔다
3) 1번 노드부터 current_node로 두고dfs 실행을 한다
4) graph를 참조해서 current_node의 neighbor_node를 찾는다
5) neighbor_node는 2가지로 구성되어 있다. parent_node & child node
6) neighbor_node를 순서대로 iterate해서 neighbor_node의 부모노드가 있는지 확인한다.
7) 값이 0이면 부모노드가 확인되지 않았다는 뜻이고, 즉 그 노드를 방문하지 않았다는 뜻이다.
8) 그럼 아직 안 가본 그 이웃 노드는 자식 노드기 때문에 이웃노드의 parent값에 current_node를 넣는다.
9) 재귀적으로 이를 실행한다.

parent = [0] * (N+1)
parent[1] = 1

def dfs(current_node, graph, parent):
  for neighbor in graph[current_node]: # graph를 참조해서 current_node의 이웃을 찾는다
    if parent[neighbor] == 0 : # 부모노드가 확인되지 않는다 즉 노드를 방문하지 않았다
      parent[neighbor] = current_node  # 이웃의 부모로 자신을 저장
      dfs(neighbor, graph, parent) # 해당 이웃 graph 부터 재귀적으로 실행

dfs(1, graph, parent)

출력

for i in parent[2:]:
  print(i)