[백준] 트리의 부모 찾기(11725번)

[출처] https://www.acmicpc.net/

알고리즘 분류 : 그래프 이론, 그래프 탐색

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입출력

접근

간단한 그래프 탐색 문제다.

접근 아이디어는 다음과 같다.

1. 주어진 입력으로 트리를 만든다(2차원 배열로 만들고 인덱스를 1부터 사용함)'
2. bfs 탐색을 하면서 인접한 노드를 방문처리 하면서, 방문처리 리스트 값에 부모의 값을 넣는다.
3. 반환된 방문처리 리스트의 값을 순서대로 2부터 출력한다.

아주 단순한 문제였다.
시작노드를 1번노드로 해서 그래프를 탐색했다.

인접한 노드들은 방문한 적이 없다면 현재노드(부모노드가 된다.)번호를 방문 리스트의 값에 넣는다.

최종적으로 방문 리스트(코드에서 visited)를 반환하고 2번 노드부터 순서대로 출력하면 된다.

import sys
from collections import deque

'''입력'''
#노드의 개수
n = int(sys.stdin.readline())

#그래프 생성 - 인덱스를 1부터 쓰기 위해서 n+1개만큼 생성함.
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    #간선 정보를 입력받음
    a,b = map(int,sys.stdin.readline().split())

    graph[a].append(b)
    graph[b].append(a)


#bfs함수 정의
def bfs(start_node,graph):

    visited = [0 for _ in range(len(graph))]

    need_visited = deque(list())

    #시작노드 넣기
    need_visited.append(start_node)

    visited[start_node] = 1

    while need_visited:

        current_node = need_visited.popleft()

        for i in graph[current_node]:
            #방문한 적이 없다면 탐색
            if visited[i] == 0:
                visited[i] = current_node
                need_visited.append(i)

    return visited

#탐색 결과
result = bfs(1,graph)

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

결과

기본적인 트리 탐색을 묻는 문제였다.