[백준] 11725 Python파이썬 풀이

문제에서 트리의 루트가 1번으로 주어졌다. BFS나 DFS를 이용해 1번부터 시작해서 노드들을 순회하면 된다. 

i) DFS 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n = int(input())
parent = [0] * (n+1) # 부모 노드를 저장한다.
graph = [[] for _ in range(n+1)]

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

def DFS(start, graph, parent):
    for i in graph[start]:
        if parent[i] == 0:
            parent[i] = start
            DFS(i, graph, parent)

DFS(1, graph, parent)
# 출력
for i in range(2, n+1):
    print(parent[i])

Union-find를 맨 처음 떠올렸다. 그렇지만 이 경우에는 graph 정보만 주어진다. 두 정점 간 어떤것이 부모노드인지 바로 주어지지 않는다.

 graph 정보를 입력 받아서 graph(=여기서는 문제에서의 tree)를 만든다. 

DFS는 1부터 탐색시작하면 된다. 그리고 여기서 조금 실수할 수 있는데, 출력할 때 문제에서 2부터 출력하라고 했다 ㅋㅋ

parent가 아직 0이면 start로 갱신해준다 !! 맨 꼭대기 루트노드를 찾을필요는 없으니까 갱신은 한번이면 충분하다 

ii) BFS

위랑 같은 원리인데 queue를 사용한다는 점이 다르다.

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
parent = [0] * (n+1) # 부모 노드를 저장한다.
graph = [[] for _ in range(n+1)]

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

def BFS():
    queue = deque()
    queue.append(1) # root
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if parent[i] == 0:
                parent[i] = node
                queue.append(i)

BFS()

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