11725. 트리의 부모 찾기 (Python)

11725번: 트리의 부모 찾기

 

풀이

 각 노드에 연결된 노드들을 담아놓는 배열(nodes)을 만들어준다. 입력으로 5 3을 받으면 nodes[5]에 3을 추가해주고 nodes[3]에 5를 추가해주는 방식으로 nodes 배열을 채워준다. 

 

 루트 노드가 1이라고 했으므로 1부터 큐에 담아서 각 노드에 연결되어 있는 노드들에 대해서 탐색한다. nodes[1]에 있는 노드들을 차례대로 큐에 담아주는데 이때 nodes[1]에 있는 노드들의 부모는 1번 노드이므로 부모 노드로 1을 담아준다. 이와 같은 방식으로 큐를 돌면서 노드들의 부모 노드를 찾아주고 마지막에 부모 노드들을 출력해 주면 된다.

 

 

코드

from collections import deque

if __name__ == '__main__':
    N = int(input())
    nodes = [[] for _ in range(N+1)] # 각 노드에 연결 되어 있는 노드들
    answer = [1] * (N+1) # 각 노드의 부모 노드
    visited = [False] * (N+1) # 노드 방문 여부 체크 

    # 입력에 따라 nodes 배열을 채워줌
    for i in range(N-1):
        a, b = map(int, input().split())
        nodes[a].append(b)
        nodes[b].append(a)

    q = deque()
    q.append(1) # 루트 노드부터 시작

    while q:
        now = q.popleft()

        # 이미 체크한 노드면 건너뛴다
        if visited[now]:
            continue
        visited[now] = True

        # now 노드에 연결 되어 있는 노드들에 대해서 탐색하는데 이미 방문한 노드면 탐색하지 않는다.
        # nodes[now]에 있는 노드들은 부모 노드로 now 노드를 갖고 있는 것이므로 부모 노드를 설정해준다.
        for node in nodes[now]:
            if visited[node]:
                continue

            answer[node] = now
            q.append(node)

    for i in range(2, N+1):
        print(answer[i])