[백준 2024/02/12] 11725번 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

1. 접근 방법

이번 문제는 두 정점이 연결된 것들을 정리하면서 부터 시작이 되었다.

 

위 예제에 대해서 defaultdict(list) 를 통해 정리를 하였다.

1번 노드 : 1-6, 1-4

2번 노드: 2-4

3번 노드: 3-6, 3-5

4번 노드: 4-1, 4-2, 4-7

5번 노드: 5-3

6번 노드: 6-1, 6-3

7번 노드: 7-4

defaultdict(<class 'list'>, {1: [6, 4], 6: [1, 3], 3: [6, 5], 5: [3], 4: [1, 2, 7], 2: [4], 7: [4]})

이렇게 정리가 되었다. 

 

이후 parent라는 dictionary를 선언해 주었다. parent = { 1: 0} -> 1번 노드의 부모는 없기 때문에 0으로 적어주었다.

이후 to_visit 이라는 list를 선언해주어, 방문한 노드를 관리해 주었다. 1번은 루트 노드로서, 이미 방문을 완료하였기에, to_visit = [1] 로 적어주었다.

 

i = 0 으로 선언, 

while len(parent) != node_len 을 실행해주었고, to_visit[i]을 통해 맨 앞에 있는 값을 가져와 주었다. -> 1 

( 맨 앞에 있는 것을 가져와주는 이유는, 맨 앞에 있을수록 트리 상에서 위쪽에 위치한 것이기 때문이다.)

이후 defaultdict에서 1번 key의 value를 하나씩 읽어왔다. 위 경우 [6, 4] 를 읽어오게 된다.

6이 to_visit에 없을 경우, parent[6] = 1 로 추가해주었다. 이후, to_visit.append(6) 또한 해주었다. 4도 동일하다.

만약 있을 경우, 다시 방문 할 이유가 없기 때문에 넘어가 주었다.

 

이후 i += 1 을 하여, 1 다음으로 찾은 노드에 대해서 다시 자식 노드를 찾기 시작했다. -> to_visit[1]

 

이런 식으로 while 문을 반복해주었다.

 

처음에는

for node not in to_visit

 

을 통해서, 특정 노드 방문 여부를 알아보려고 했다. 하지만, 이는 list에서 특정 값의 유무를 찾는 것이기 때문에 시간 복잡도가 O(n) 이 되게 된다. 이를 개선하기 위해서, 

if node not in parent:

를 통해 방문 여부를 알아보고자 하였다. to_visit -> parent로 바꾸어주기만 하였음에도 합격, 불합격이 갈렸다. 그 이유는 parent는 dictionary이기 때문에 hash table을 사용하게 되고 O(1) 의 시간복잡도를 가지기 때문이다.

 

아래는, 처음에 시간 초과가 된 코드이다. 즉, to_visit을 이용한 코드이다.

from collections import defaultdict


node_len = int(input())
node_dict = defaultdict(list)

for i in range(node_len - 1):
    start, end = map(int, input().split())
    node_dict[start].append(end)
    node_dict[end].append(start)


dict = defaultdict(int)
order = [1]
i = 0

while len(dict) != node_len -1:
    for node in node_dict[order[i]]:
        if node not in order:
            order.append(node)
            dict[node] = order[i]
    i += 1

for i in range(2, node_len + 1, 1):
    print(dict[i])

 

 

2. 코드

from collections import defaultdict


node_len = int(input())
node_dict = defaultdict(list)

for i in range(node_len - 1):
    start, end = map(int, input().split())
    node_dict[start].append(end)
    node_dict[end].append(start)


parent = defaultdict(int)
parent[1] = 0
to_visit = [1]
i = 0

while len(parent) != node_len:
    for node in node_dict[to_visit[i]]:
        if node not in parent:
            to_visit.append(node)
            parent[node] = to_visit[i]
    i += 1

for i in range(2, node_len + 1, 1):
    print(parent[i])