백준: 11725 트리의 부모 찾기

문제

11725번: 트리의 부모 찾기

 

문제 풀이

 2부터 n -1 까지의 노드에 대한 부모를 찾는 문제이다. 이는 다른 그래프 문제에서 방문 여부를 탐색하는 것을 활용하면 쉽게 풀 수 있다. BFS를 통해 특정 노드를 방문할 때, 방문되지 않았다면 해당 노드의 부모는 현재 노드가 부모가 된다. 만약 예제 입력 1과 같을 경우, BFS로 통해 탐색하게 되면 1번 노드의 자식 노드들은 각각 4, 6이고 최초 방문 상태이므로 부모 노드가 1 임을 체크할 수 있다. 이처럼 모든 노드에 대해 방문하지 않은 경우 현재의 부모를 체크해두면 트리의 부모를 찾을 수 있다.

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        parent = q.popleft()
        for child in graph[parent]:
            if not visited[child]:
                visited[child] = parent
                q.append(child)

    print('\n'.join(map(str, visited[2:])))


if __name__ == '__main__':
    n = int(stdin.readline())
    visited = [0] * (n + 1)
    visited[1] = 1
    graph = [[] for _ in range(n + 1)]

    for _ in range(n - 1):
        node, connect = map(int, stdin.readline().split())
        graph[node].append(connect)
        graph[connect].append(node)

    bfs(1)