[알고리즘] 11725 트리의 부모 찾기

DongGyu Jung·2022년 4월 3일
0
post-thumbnail

게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.

※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.

❓ 문제

백준 온라인 저지 (Baekjoon Online Judge) :


❗ 풀이

My Code

메모리 : 54228KB
시간 : 384ms

트리 루트를 1이라고 가정 : 시작 노드

deque를 활용해서 풀이했고
입력되는 경로에 대해
graph를 만들어 서로 갈 수 있는 노드들 양방향에 서로를 넣어주고

popleft되어 나오는 노드값들 마다
갈 수 있는 노드들을 조회하는 for문을 활용해서
최초로 방문하는 노드의 부모로 자신을 넣어준 후,

도착 노드값을 다시 큐에 삽입하는 형태로 풀이하였다.

마지막으로
출력조건이
2번 노드부터 순서대로 출력하는 것이기 때문에
Parent[2:]를 사용하였다.

import sys
input = sys.stdin.readline
N = int(input())
visited = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for _ in range(N-1) :
    p, c = map(int,input().split())
    graph[p].append(c)
    graph[c].append(p)
Parent = [i for i in range(N+1)]
root = 1
from collections import deque
q = deque([root])
visited[root] = 1
while q :
    node = q.popleft()
    for v in graph[node] :
        if visited[v] == 0 :
            q.append(v)
            Parent[v] = node
            visited[v] = 1
for p in Parent[2:]:
    print(p)

0개의 댓글