11725. 트리의 부모 찾기

업데이트 시간 : 2023-02-28 00:55:21 +0000

[Silver II] 트리의 부모 찾기 - 11725

문제 링크

성능 요약

메모리: 78916 KB, 시간: 4388 ms

분류

그래프 이론(graphs), 그래프 탐색(graph_traversal), 트리(trees), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)

문제 설명

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

입력

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

출력

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

💡 Solutions

📄 트리의 부모 찾기.py

import sys
sys.setrecursionlimit(10000000)

N = int(input())
rlt = [list(map(int,input().split())) for i in range(N-1)]

nodes = [list() for o in range(N+1)]
for i in range(N-1):
    nodes[rlt[i][0]].append(rlt[i][1])
    nodes[rlt[i][1]].append(rlt[i][0])
is_traveled = [False for _ in range(N+1)]
ans = [0 for _ in range(N+1)]
def inorder(v):
    # if v= 1 일 겨우에는 -> 6번하고 4번이
    # if v= 6 일 경우에는 -> 1하고 3 // 아니? 1은 부모아니였어?
    for node in nodes[v]: # -> 모르겠으니까 for문을 돌린거야
        if is_traveled[node] == True:
            continue
        is_traveled[node] = True
        inorder(node) # -> 6번하고 4번 탐색 할 수 있겠찌
        # 우리가 원하는 수식 == 이친구의 부모 노드가 뭐야!!!
        # 이곳에서 우리는 알 수 있다!
        ans[node] = v

    
is_traveled[1] = True
inorder(1)
    
for idx in range(2,N+1):
    print(ans[idx])