백준 11725번 트리의 부모 찾기

정보

문제 바로가기 [클릭]

난이도: Silver2

관련 개념: #그래프이론 #그래프탐색 #깊이 우선 탐색 #너비 우선 탐색 #트리

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

7
1 6
6 3
3 5
4 1
2 4
4 7

출력

4
6
1
3
1
4

---

예제 입출력 2

입력

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

출력

1
1
2
3
3
4
4
5
5
6
6

---

코드(파이썬)

import sys


graph = dict()
tree = dict()
queue = [1]
visited = set()

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

for line in sys.stdin.readlines():
    s, e = map(int, line.split())
    
    if s in graph:
        graph[s].append(e)
    else:
        graph[s] = [e]
    if e in graph:
        graph[e].append(s)
    else:
        graph[e] = [s]

while queue:
    for _ in range(len(queue)):        
        i = queue.pop()
        
        if i not in visited:
            queue.extend(graph[i])
            visited.add(i)
            
            for v in graph[i]:
                graph[v].remove(i)
                tree[v] = i

sys.stdout.write('\n'.join([str(tree[i]) for i in range(2, n+1)]))

---

특이사항

• 자식이 키이고 부모를 값으로 하는 tree 딕셔너리 이용
• 내 코드(77,044KB, 404ms)에 비해 우수한 코드(바로가기, 49,356KB, 344ms)와 비교

  • # 11725 트리의 부모 찾기
    
    from sys import stdin as s
    
    input = s.readline
    
    n = int(input())
    connection = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        x, y = map(int, input().split())
        connection[x].append(y)
        connection[y].append(x)
    parents = [0] * (n + 1)
    visited = [False] * (n + 1)
    visited[1] = True
    start = [1]
    while start:
        new_start = []
        for now in start:
            for can_go in connection[now]:
                if not visited[can_go]:
                    parents[can_go] = now
                    visited[can_go] = True
                    new_start.append(can_go)
        start = new_start
    for i in parents[2:]:
        print(i)
    
    

  • 트리 생성
    • 기존: graph 딕셔너리에 저장 뒤 이를 이용하여 tree 딕셔너리 작성
    • 개선: connection 리스트에 저장 뒤 이를 이용하여 parents 리스트 작성
  • 방문 여부
    • 기존: 셋
    • 개선: 리스트

    • 동일한 기존 코드에서 리스트와 셋을 비교한 결과

      구분	메모리	시간
      리스트	71,172ms	416ms
      셋	77,044ms	404ms

    • 차후 풀이에서는 리스트 사용할 것

---

참고문헌

-