2019.02.02) 백준 11725번 풀이 (PyPy3)

dfs로 구현을 했는데 최적화를 못해 시간초과로 계속 빠꾸를 먹었다.

수정 전 소스

node_list = dict()
parent = dict()
c = int(input())
 
for i in range(c):
    node_list[i + 1] = list()
for i in range(c - 1):
    a, b = input().split(' ')
    node_list[int(a)].append(int(b))
    node_list[int(b)].append(int(a))
 
visited = list()
to_visit = [1]
 
while to_visit:
    now = to_visit.pop()
    for i in node_list[now]:
        if i not in visited:
            parent[i] = now
            visited.append(now)
            to_visit.append(i)
 
for i in range(2, c + 1):
    print(parent[i])

visited를 계속 in으로 쓸모없는 탐색을 한것이 시간초과의 원인이었다.

아래는 맞은 소스

node_list = dict()
parent = dict()
c = int(input())
 
# 그래프 제작
for i in range(c):
    node_list[i + 1] = list()
for i in range(c - 1):
    a, b = input().split(' ')
    node_list[int(a)].append(int(b))
    node_list[int(b)].append(int(a))
 
# 지나간건 True 안지나간건 False
visited = [False for i in range(c)]
# 1부터 지나감
to_visit = [1]
 
while to_visit:
    # dfs로 구현하기 위해 맨뒤의 값을 사출
    now = to_visit.pop()
    # 그 값과 연결된 자식+부모를 반복문으로 돔
    for i in node_list[now]:
        # 방문 안한게 걸리면 방문
        if not visited[i-1]:
            # 자식과 부모 저장
            parent[i] = now
            visited[i-1] = True
            to_visit.append(i)
 
# 출~력
for i in range(2, c + 1):
    print(parent[i])