백준 11725번 - 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

---

트리의 부모 찾기 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

256 MB

18862

8013

5971

43.501%

문제

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

입력

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

출력

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

---

[ 문제 설명 ]

루트 노드는 1번이라 가정하고 연결된 노드를 무작위로 주어질 때, 각 트리의 부모를 찾는 문제.

 

우선 문제를 이해하기 위해 1을 루트 노드로 설정하고 노드의 그림을 예제를 통해 그려보면 이해하기 쉽다.

그림으로 설명하겠다.

 

그림 1 - 부모 노드 찾기 설명

그림 2 - 부모 노드 찾기 설명

왜 tree 배열을 딕셔너리로 초기화했는지 이해가 가시나요?

딕셔너리를 이용해 인덱스 부분과 node를 일치시켜서 편하게 코딩하기 위함이지요.

---

[ 코드 ]

 

import sys
from collections import deque

n = int(sys.stdin.readline())

parent = [0] * (n + 1)
parent[1] = 1


tree = {}
for i in range(1, n+1):
    tree[i] = []

for j in range(n - 1):
    conNode1, conNode2 = map(int, input().split())
    tree[conNode1].append(conNode2)
    tree[conNode2].append(conNode1)
# print(tree)
# BFS
def BFS(q):
    while q:
        #print(q, end="->")
        node = q.popleft()
        #print(node, end="=>")
        for kid in tree[node]:
            if not parent[kid]:
                parent[kid] = node
                q.append(kid)

    return parent

q = deque([1])
BFS(q)
for ch in parent[2:]:
    print(ch)

 

 

---

후기

 

딕셔너리를 통해 좀 더 간편하게 코딩할 수 있는 스킬을 배운거 같다.

복습을 통해 좀더 확실하게 이해가 된 거 같다...