https://www.acmicpc.net/problem/11725
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
예제 1과 2를 트리로 만들어보면 위와 같다.
첨엔 그냥 딕셔너리에 트리 연결 정보를 단방향으로 넣었더니 아예 1번예제가 되지 않았다.
이렇게 양방향으로 넣고나서 엄청나게 비효율적인 탐색을 했더니 시간초과가 떴다.
트리를 돌면서 자식에 찾는 자식이 있을때까지 $n^2$으로 도는...
from collections import defaultdict
tree = defaultdict(list)
for _ in range(int(input())-1):
p, c = map(int, input().split())
tree[p].append(c)
tree[c].append(p)
for i in range (2, len(tree)+1):
for k, v in tree.items():
if i in v:
print(k)
break그래서 너비우선 탐색으로 풀게 되었다
parent배열을만들고, 탐색을 하면서 부모가 누군지 밝혀지면 해당 인덱스에 기록하고
마지막에 배열을 순서대로 출력하면 해결!
그런데.......너무너무너무 느리게 통과했다...정말 겨우겨우 시간초과가 안 된 수준...
통과되고 빠른 사람들의 코드를 보니, 내가 입력함수를 안 바꾼 걸 깨달았다.
입력과 출력방식까지 바꾸자 324ms가 나왔다.
from collections import defaultdict, deque
from sys import stdin
def input():return stdin.readline()
tree = defaultdict(list)
for _ in range(int(input())-1):
p, c = map(int, input().split())
tree[p].append(c)
tree[c].append(p)
parent = [0] * (len(tree.keys())+1)
def bfs(root):
q = deque()
q.append(root)
while q:
node = q.popleft()
for child in tree[node]:
if parent[child] == 0:
parent[child] = node
q.append(child)
bfs(1)
print("\n".join(map(str,parent[2:])))