[Python] 백준 풀기 11725 - 트리의 부모 찾기

파이썬 백준 11725번

실버2

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

11725번: 트리의 부모 찾기

 

 

 

 

 

문제 보기

분류: 그래프 탐색, 트리, 너비 우선 탐색

 

 

 

 

 

문제 풀기

루트를 1로 정했기 때문에 1을 부모 노드로 시작하여 그 바로 아래 노드는 1의 자식 노드가 되면서 그 다음 아래 노드의 부모가 된다. 이 규칙을 적용하여 너비 우선 탐색을 이용하여 문제를 해결하였다.

 

 

예제 1을 그림으로 나타내면 위와 같다.

 

 

위에서 부터 부모 노드 방문을 표시하고 그 아래 자식 노드를 하나씩 deque 에서 꺼내어 부모 노드가 될 수 있는지 (그 아래 방문하지 않은 노드, 다시 말해 미래의 자식 노드)가 있는지를 확인한다. 만약 있다면 그 노드는 미래의 부모 노드가 되기때문에 result 리스트에 index 와 노드 번호에 맞게 저장한다.

 

 

 

 

 

코드 보기

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

def fnBFS(graph, v, visited):
    que = deque([v])
    
    visited[v] = True
    while que:
        x = que.popleft()
        for i in graph[x]:
            if not visited[i]:
                result[i] = x
                que.append(i)
                visited[i] = True
        print(f'que: {que}')          # test print
        print(f'visited: {visited}')          # test print
        print(f'result: {result}')           # test print


if __name__ == "__main__":
    N = int(inputdata().strip())
    graph = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        a, b = map(int, inputdata().split())
        graph[a].append(b)
        graph[b].append(a)
    print(f'graph: {graph}')            # test print
    
    visited = [False] * (N + 1)
    result = [0] * (N + 1)
    
    fnBFS(graph, 1, visited)
    
    for i in range(2, N + 1):
        print(result[i])



# 7
# 1 6
# 6 3
# 3 5
# 4 1
# 2 4
# 4 7


# graph: [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]]

# que: deque([6, 4])
# visited: [False, True, False, False, True, False, True, False]
# result: [0, 0, 0, 0, 1, 0, 1, 0]

# que: deque([4, 3])
# visited: [False, True, False, True, True, False, True, False]
# result: [0, 0, 0, 6, 1, 0, 1, 0]

# que: deque([3, 2, 7])
# visited: [False, True, True, True, True, False, True, True]
# result: [0, 0, 4, 6, 1, 0, 1, 4]

# que: deque([2, 7, 5])
# visited: [False, True, True, True, True, True, True, True]
# result: [0, 0, 4, 6, 1, 3, 1, 4]

# que: deque([7, 5])
# visited: [False, True, True, True, True, True, True, True]
# result: [0, 0, 4, 6, 1, 3, 1, 4]

# que: deque([5])
# visited: [False, True, True, True, True, True, True, True]
# result: [0, 0, 4, 6, 1, 3, 1, 4]

# que: deque([])
# visited: [False, True, True, True, True, True, True, True]
# result: [0, 0, 4, 6, 1, 3, 1, 4]


# 4
# 6
# 1
# 3
# 1
# 4