11725번. 트리의 부모 찾기 (Python)

http://boj.kr/11725 

11725번: 트리의 부모 찾기

 

우선 주어진 입력을 인접 딕셔너리로 바꾼다. 주어진 입력에 방향이 없으므로 양쪽 다 인접 딕셔너리에 추가해야 한다.

그런 다음 루트인 1에서부터 find_parent 를 시작한다.

find_parent에서는 1의 자식을 순회하면서 그 자식의 부모가 1이라고 표시한다.

 

첫번째 테스트케이스에서 1의 자식은 4, 6이다. line 6에서 4와 6을 차례로 순회하게 되는데, 

line 8에서 각각 parent[4] = 1, parent[6] = 1 이라고 표시하게 되서 부모를 저장할 수 있게 된다.

그리고 4와 6을 다시 부모 삼아서 find_parent를 호출한다. 더 이상 자식이 없을 때까지 호출된다.

 

1의 자식이 4와 6이라고 했지만 주어진 입력을 인접 딕셔너리로 바꿀 때 양방향으로 추가해줬으므로 4와 6의 자식이 1이기도 한데, visited 배열에 방문 표시를 해줘서 사이클이 생기지 않도록 한다.

import sys


def find_parent(node, graph):
    visited[node] = True
    for child in graph[node]:
        if not visited[child]:
            parent[child] = node
            find_parent(child, graph)


def solution(lst):
    tree = {i: [] for i in range(1, n+1)}  # 인접 딕셔너리 (0은 제외)
    for a, b in lst:
        tree[a].append(b)  # 주어진 입력에 방향이 없으므로 양쪽 다 추가
        tree[b].append(a)

    visited[1] = True
    find_parent(1, tree)  # 루트=1에서부터 출발

    for i in range(2, len(parent)):
        print(parent[i])


sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
n = int(input())
adj = [list(map(int, input().split())) for _ in range(n-1)]  # 입력
visited = [0 for _ in range(n+1)]  # 0(제외), 1~7
parent = [0 for _ in range(n+1)]
solution(adj)