[백준/python] 11725번 트리의 부모 찾기

11725번: 트리의 부모 찾기 (acmicpc.net)

문제 풀이

입력이 길어 input이 아닌 sys모듈의 stdin.readline 사용

모든 노드의 연결구조를 봐야한다고 생각해서 dfs로 풀긴했지만, bfs로 푸는 것도 오답이 아니라고 생각함. 입력받기는 딕셔너리에 저장. 이때 정점 u와 v가 연결되어있다면 딕셔너리의 키값으로 둘 다 저장함. 이다음 깊이우선탐색을 하는데, 방문여부를 파악하는 동시에 답을 저장함. 이를 위해 딕셔너리 이용. 깊이우선이므로 스택(후입선출) 만들어서 루트노드인 1을 저장. 스택이 빌 때까지 while 반복. 스택에서 pop을 하며 그 노드를 node에 저장. 이 노드가 이미 방문된 노드라면 continue, 아니라면 방문했다는 의미로 visit에 저장. 루트노드인 1은 그냥 1이라 저장해주지만 다른노드들은 연결되어있으면서 이미 방문된 노드를 저장(부모노드). 그리고 연결된노드들을 모두 스택에 삽입. 모든 과정이 끝나면 for문으로 2부터 n까지 딕셔너리에서 불러서 출력.

import sys
input = sys.stdin.readline
n=int(input())
di={}
for _ in range(n-1): #di 입력받기
    u,v=map(int,input().split())
    if u in di: di[u].append(v)
    else: di[u]=[v]
    if v in di: di[v].append(u)
    else: di[v]=[u]

ans_visit={}
st=[1]

while st:
    node=st.pop()
    if node in ans_visit: continue
    st.extend(di[node])
    if node==1: ans_visit[node] = 1
    else:
        for x in di[node]:
            if x in ans_visit:
                ans_visit[node] = x

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