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가 생긴 노드들을 다시 큐에 넣고 돌아가면서 찾는다.
- 노드들이 연결된 엣지 중에서 부모가 아직 안정해진 엣지만 부모를 정해준다.
Author And Source
이 문제에 관하여(11725. 트리의 부모 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@youngjin_kim2/11725.-트리의-부모-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)