[11725] 트리의 부모찾기 in python

 

처음에 문제를 보고 헤맸던 부분은

부모 - 자식 순으로 입력이 주어지는 줄 알았다.

1번 노드가 루트 노드라는 게 문제에 딱 나와있는데,

그걸 놓쳐서 ㅠ..

 

어차피 양방향 그래프로 받게 되면

상관이 없음

 

 

DFS를 이용하여 풀었다.

 

1번 노드부터 탐색을 시작해야한다고 문제에 나와있으므로

1번 노드부터 탐색 시작

 

그래프 입력받은 건

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

 

1번 노드 : [6.4]

2번 노드 : [4]

3번 노드 : [6,5]

4번 노드 : [1,2,7]

5번 노드 : [3]

6번 노드 : [1,3]

7번 노드 : [4]

 

1번 노드를 보면

6번과 4번 노드와 연결되어 있다.

 

6번 노드와 4번 노드는 아직 방문을 하지 않은 노드이므로

1번 노드의 자식 노드가 되는 셈

 

즉

A번 노드 : [x,y]

x번 노드가 아직 방문처리가 되지 않은 노드라면?

x번 노드의 부모는 A번 노드이다.

 

y번 노드가 이미 방문처리가 된 노드라면?

y번 노드의 자식이 A번 노드인 셈.

 

 

dfs(1)

1번 노드와 연결된 노드는 6번 노드와 4번 노드

1번 노드 방문처리

6번 노드, 4번 노드의 부모 노드는 1번 노드

 

 

dfs(6)

6번 노드 <-> 1번 노드, 3번 노드

6번 노드 방문처리

1번 노드는 이미 방문했으므로 패스

3번 노드의 부모는 6번 노드

 

 

dfs(3)

3번 노드 <-> 6번, 5번 노드

3번 노드 방문처리

6번 노드 패스

5번 노드의 부모는 3번 노드

 

df(5)

5번 노드 <-> 3번 노드

5번 노드 방문처리

3번 노드 패스

 

dfs(4)

4번 노드 <-> 1번,2번,7번

4번 노드 방문처리

1번 패스

2번 노드의 부모는 4번 노드

7번 노드의 부모는 4번 노드

 

dfs(2)

2번 노드 <-> 4번 노드

2번 노드 방문처리

4번 패스

 

dfs(7)

7번 노드 <-> 4번 노드

7번 노드 방문처리

7번 노드의 부모는 4번 노드

 

 

import sys
sys.setrecursionlimit(10**9)
n=int(input())
graph=[[] for _ in range(n+1)]
for _ in range(n-1):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
answer=[0 for _ in range(n+1)]
visited=[False for _ in range(n+1)]
def dfs(node):
    visited[node]=True
    for i in graph[node]:
        if not visited[i]:
            answer[i]=node
            dfs(i)


dfs(1)
for i in range(2,n+1):
    print(answer[i])