[BOJ_11725] 트리의 부모 찾기 (python)

11725번: 트리의 부모 찾기

 

✅ 문제 설명

트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제다.
입력 => 첫째줄에 노드의 수 N이 주어지고, 둘째 줄부터 트리 상에서 연결된 두 정점이 주어진다.
ex) 아래 그림에서 왼쪽과 같은 입력으로 트리를 그려보면 그림의 오른쪽과 같은 트리를 얻을 수 있다.

✅ 접근 방식

• 트리의 특징 상, 루트노드에서부터 탐색을 수행하면 부모노드를 거치지 않고선 자식노드에게 갈 수 없다.
• 루트노드에서 dfs나 bfs로 트리를 탐색하면서 "새롭게 탐색된 노드의 부모노드 = 현재 노드"로 저장해 준다.

✅ 코드

# 트리의 부모 찾기

import sys
from collections import deque

N = int(sys.stdin.readline())

# 트리 생성
graph = [set() for i in range(N)]
for i in range(N - 1):
    A, B = map(int, sys.stdin.readline().split())
    graph[A - 1].add(B)
    graph[B - 1].add(A)

visited = [0 for i in range(N)] # 0: 방문안함 / 0이 아닌 숫자: 루트번호

# bfs 수행
queue = deque([1])
while queue:
    n = queue.popleft()
    for adj in graph[n - 1]:
        if visited[adj - 1] == 0:
            visited[adj - 1] = n
            queue.append(adj)


for i in range(1, len(visited)):
    print(visited[i])

• graph = [set() for i in range(N)] -> 그래프를 인접리스트로 구현해주었다.
• visited 배열은 0이 담겨있을 때는 방문 안 함, 다른 숫자가 담겨있을 때는 방문했음을 뜻하며 그 숫자는 해당 노드의 부모노드를 뜻한다. 노드 개수 N만큼의 길이를 갖는 초기값 0인 리스트로 선언해줬다. 탐색을 하면서 해당노드의 부모노드 번호로 업데이트 되게된다.
• 루트노드(=1) 부터 bfs를 수행해주었다.

❇️ 코멘트

• 옛날 코드를 보면 bfs를 이렇게 짰었다. (큐에 들어가 있는 애도 visited 여부를 확인한 다음 bfs를 수행했다.)

while queue:
    n = queue.popleft()
    if visited[n-1] == 0: # not visited
        visited[n-1] = 1
        for adj in graph[n-1]:
            if visited[adj-1] == 0:
                visited[adj-1] = n
                queue.append(adj)

• 근데 그렇게 하지 않고, 이렇게 바로 동작을 수행해도 되는 듯하다..! 더 알아봐야겠다.

while queue:
    n = queue.popleft()
    for adj in graph[n - 1]:
        if visited[adj - 1] == 0:
            visited[adj - 1] = n
            queue.append(adj)

• bfs말고 dfs로도 풀어봐야겠다. 저번에 풀었을 땐 dfs로 푸니까 재귀호출의 최대깊이를 초과해 런타임에러가 났었는데 다른 블로그들을 보니 dfs로 풀 수도 있는 것 같다.
• 이 문제를 풀때 dfs/bfs 중 뭐가 적합한지 생각해봐야겠다.