백준 11725 트리의 부모 찾기 #python # BFS

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

11725번: 트리의 부모 찾기

 

✍️ 처음 나의 풀이

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

n = int(input())
visited = [False]*(n+1)    # 방문 여부 표시
l = [0]*(n+1)  # 루트로 부터의 거리
graph = [[] for i in range(n+1)]

for _ in range(n-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def bfs():

    queue = deque()
    visited[1] = True #루트노드 방문처리
    queue.append(1)     # 루트노드 큐에 삽입
    l[1] = 0

    while queue:
        x = queue.popleft()          #큐에서 하나 pop
        for i in graph[x]:          # pop한 노드의 주변노드 중에서
            if not visited[i]:       # 아직 방문 안한것들
                queue.append(i)     # 큐에 추가
                visited[i] = True   # 방문처리
                l[i] = l[x]+1       # 주변노드 거리 = 현재노드 거리 + 1


bfs()

for i in range(2, n+1):

    if len(graph[i]) == 1:
        min = graph[i][0]
    else:
        min = graph[i][0]
        t = l[min]

        for j in graph[i]:
            if t > l[j]:
                t = l[j]
                min = j

    print(min)

BFS로 탐색하면서 루트로부터 떨어진 거리를 배열 l에 저장한 뒤,

주변노드 중에서 l[i]값이 가장 작은 것을 출력했다.

test case 답은 잘 나왔는데 너무 복잡하게 생각한 거였다.

 

✍️ 좀 더 간단한 풀이

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

n = int(input())
visited = [False]*(n+1)
graph = [[] for _ in range(n+1)]
answer = [0]*(n+1)   #답을 저장할 배열

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


def bfs(graph, v, visited):
    queue = deque([v])
    visited[v] = True

    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                answer[i] = x
                visited[i] = True
                queue.append(i)


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

방문처리를 하면서 큐를 활용해 탐색하면

자연스럽게 부모노드 x -> 자식노드들 i 순으로 접근하게 되는 성질을 이용한것이다.

좀 더 직관적이고 bfs다운 풀이인듯.