11725. 트리의 부모 찾기

문제 링크

11725. 트리의 부모 찾기

문제 코드

from collections import deque
import sys

node = int(input())
parent = [[]for i in range(node+1)]
edge_num = [0]*(node+1)
result = [0]*(node+1)
for i in range(node-1):
    num_list = list(map(int, sys.stdin.readline().split()))

    parent[num_list[0]].append(num_list[1])
    parent[num_list[1]].append(num_list[0])

edge_num[0] = 1
edge_num[1] = 1

que = deque()
que.append(1)

while len(que)>0:
    tmp = que.popleft()

    for i in parent[tmp]:
        if edge_num[i] == 0:
            edge_num[i] = tmp
            que.append(i)


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

문제 풀이

• 처음에는 그래프 n*n 을 만들어서 BFS 방식으로 풀려고했다.
• 이 방식은 메모리를 너무 많이 잡아 먹음
• 두번째로는 엣지를 넣으면서 1인게 있으면 parent를 1로 설정해주고 아닌거를 que에 넣도록 했다.
• 시간이 너무 많이 걸리는 문제 발생
• 리스트의 배열을 만드는게 가능하다는 것을 알게됨
• 리스트의 배열을 만들어서 엣지 하나하나를 집어 넣을때마다 양끝 노드를 서로 추가해준다.
• 다 넣고나서 1번 노드의 자식 노드들을 찾아가서 parent를 1로 만들어준다.
• parent가 생긴 노드들을 다시 큐에 넣고 돌아가면서 찾는다.
• 노드들이 연결된 엣지 중에서 부모가 아직 안정해진 엣지만 부모를 정해준다.