백준 11725 : 트리의 부모 찾기 (Python)

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

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

예제 출력 1

4
6
1
3
1
4

---

나의 풀이

• 이 문제에서 주어지는 노드 정보를 인접 행렬 그래프로 변환하면 DFS 또는 BFS로 쉽게 부모를 찾을 수 있다. 예제 입력 1의 경우에서 살펴보면 현재 주어진 인접 행렬 그래프는 아래와 같이 표현할 수 있다. 인접 행렬 그래프에서는 노드의 부모 자식 관계를 알 수 없기에 DFS를 수행한다. 루트 노드부터 탐색하는 탑다운 방식으로 구현해 이웃 노드 중 아직 방문하지 않은 노드는 자신의 자식으로 간주하고 parents로 기록해둔다.

import sys 
sys.setrecursionlimit(10**6)


def DFS(curr_idx):
    global N,arr,visited,parents 
    for next_idx in arr[curr_idx]:
        if visited[next_idx] == False:
            parents[next_idx] = curr_idx
            visited[next_idx] = True 
            DFS(next_idx)

              
N = int(sys.stdin.readline())
# 0번째 노드는 무시 
arr = [[] for _ in range(N+1)]
for i in range(N-1):
    v1,v2 = map(int,sys.stdin.readline().split())
    arr[v1].append(v2)
    arr[v2].append(v1)
parents = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]

visited[1] = True 
DFS(1)
for i in range(2,N+1):
    print(parents[i])