[백준/파이썬] 11725번 트리의 부모 찾기

배solved.ac Class 4레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

문제 해석

루트가 1인 트리의 연결 상태가 주어진다.

루트를 제외한 이 트리의 각 노드의 부모를 구하는 문제이다.

문제 풀이

root인 1을 시작으로 bfs 탐색을 통해 부모 노드를 구해주었다.

문제 코드

import sys
from collections import deque
input = sys.stdin.readline

def solve(n, adj):
	# bfs를 통해 root부터 탐색
    visit = [0] * (n + 1)
    answer = [0] * (n + 1)
	# root인 1부터 탐색
    q = deque()
    q.append(1)
    visit[1] = 1
	
    while q:
        cur = q.popleft()
        for next in adj[cur]:
            if visit[next] == 0:
                visit[next] = 1
                answer[next] = cur
                q.append(next)

    return answer[2:]

n = int(input())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

print("\n".join(map(str, solve(n, adj))))

제출 결과