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

문제

https://www.acmicpc.net/problem/11725

풀이

• 루트 없는 트리
• 트리의 루트를 1이라고 정했을 때, 각 노드의 부모 출력

트리를 탐색하면서 각 노드의 부모를 기록하면 해결할 수 있습니다.

BFS를 사용했습니다.

    n = int(input())
    graph = [[] for _ in range(n+1)] # 트리
    visited = [0] * (n + 1) # 부모
    
    for _ in range(n-1): # 정보 저장
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)

트리 정보를 저장해 줍니다.

def bfs(start):
    queue = deque([start]) # 루트 노드 큐에 삽입
    while queue:
        node = queue.popleft() # 노드 추출
        for v in graph[node]: # 추출한 노드에 연결된 노드 탐색
            if visited[v] == 0: # 부모 노드가 없다면
                visited[v] = node # 부모 노드 설정
                queue.append(v) # 큐에 해당 노드 삽입
                
bfs(1) # 루트 노드                

루트 노드인 1을 넣어 탐색을 진행합니다.

    for i in range(2, n+1):
        print(visited[i])

2번 노드부터 순서대로 출력

코드

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

def bfs(start):
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for v in graph[node]:
            if visited[v] == 0:
                visited[v] = node
                queue.append(v)

if __name__ == "__main__":
    n = int(input())
    graph = [[] for _ in range(n+1)]
    visited = [0] * (n + 1)
    
    for _ in range(n-1):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    bfs(1)
    
    for i in range(2, n+1):
        print(visited[i])