[백준 11725 파이썬] 트리의 부모 찾기 (실버 2, 트리)

알고리즘 유형 : 트리
풀이 참고 없이 스스로 풀었나요? : 학습

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

SOLVE 1

BFS 풀이

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

N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    
q = deque()
q.append(1)

parents = [None for _ in range(N+1)] # 부모, 방문
parents[1] = 0

while q:
    cnt_node = q.popleft()
    
    for adj_node in tree[cnt_node]:
        if parents[adj_node] == None:
            parents[adj_node] = cnt_node
            q.append(adj_node)
            
for node in range(2, N+1):
    print(parents[node])

SOLVE 2

DFS 풀이

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6) # 백준의 재귀 횟수는 1000회 정도로 제한되어 있기에 풀어주기. N이 10**5니 적당히 10**6정도로.

N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    
q = deque()
q.append(1)

parents = [None for _ in range(N+1)] # 부모, 방문
parents[1] = 0

def DFS(start):
    for adj_node in tree[start]:
        if parents[adj_node] == None:
            parents[adj_node] = start
            DFS(adj_node)
            
DFS(1)
            
for node in range(2, N+1):
    print(parents[node])

SOLVE 1) 풀이 요약 (그리디 풀이)

1. tree 정보를 2차원 리스트에 담는다. 트리는 양방향 그래프이기에 a -> b, b -> a를 둘 다 담아준다.

2. BFS나 DFS로 출발 노드부터 시작하여 인접 노드를 순회하면서 부모 노드 값을 저장해나간다. 초기 값을 None으로 저장해놓고, 리스트에 None이 있는지, 그 외의 값이 있는지로 방문 여부를 체크한다.

배운 점, 어려웠던 점

• 트리의 개념, 성질 등을 배웠다.

• 트리의 표현 방법으로 평소에 늘 하던 2차원 리스트(연결 리스트 방식) 방식, 부모 정보를 저장하는 방식, 이진 트리에 대해 1차원 리스트에 노드에 번호를 붙여 인덱스로 삼는 방식, 2차원 배열로 왼쪽 자식, 오른쪽 자식을 구분하여 담는 방식을 배웠다.