트리의 부모찾기 (실버 2) [Class 4]

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

11725번: 트리의 부모 찾기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

82478

36840

25903

42.457%

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

4
6
1
3
1
4

 

문제 해결

해당 문제는 그래프 탐색 알고리즘을 사용하여 트리의 부모노드가 누구인지 찾는 문제였다. 처음에는 문제가 잘 이해가 되지 않아서 실제 입력값에 맞게 데이터를 시각화하면서 진행했다.

https://csacademy.com/app/graph_editor/

CS Academy

해당 사이트에서 입력값에 맞게 데이터를 넣어주니 아래와 같이 그래프를 시각화 할 수 있었고 해당 이미지를 보고 문제해결 방법을 생각한 결과 그냥 단순하게 1번 루트부터 시작해서 BFS 또는 DFS를 돌리면서 루트 노드의 정보를 저장해주면 되겠다라고 생각이 들었다.

 

위 생각을 그대로 수도코드로 바꾸면 아래와 같다.

1. 양방향 그래프 생성
2. 루트노드부터 BFS 탐색
- while queue
    node -> queue.pop()
    그래프[노드] -> 연결된 모든 노드 탐색
        -> 만약 최초 방문한 노드라면
            -> 해당 노드의 부모는 현재 그래프에 연결된 노드

 

조금 더 이해하기 편하게 예시로 설명하자면 아래와 같다.

• 빨강 : 부모노드
• 파랑 : 자식 노드
• 각 노드 별 부모를 저장할 정답 배열
• 방문 배열
• 큐(Queue)

1. 1번 노드에 연결된 2개의 노드 [4, 6] 탐색
2. 4, 6번 노드는 최초 방문이므로 해당 노드의 부모 노드 1를 정답 배열에 저장
   • 정답배열 : [0, 0, 0, 1, 0, 1, 0]
   • Queue : [4, 6]
   • Visit : [T, F, F, T, F, T, F]
3. 4번 노드에 연결된 2개의 노드 [2, 7] 탐색
4. 2번, 7번 노드는 최초 방문이므로 해당 노드의 부모 노드 4를 정답 배열에 저장
   • 정답배열 : [0, 4, 0, 1, 0, 1, 4]
   • Queue : [6, 2, 7]
   • Visit : [T, T, F, T, F, T, T]
5. 6번 노드에 연결된 3번 노드 탐색
6. 3번 노드는 최초 방문이므로 해당 노드의 부모 노드 6 저장
   • 정답배열 : [0, 4, 6, 1, 0, 1, 4]
   • Queue : [2, 7, 3]
   • Visit : [T, T, T, T, F, T, T]

위와 같은 형식으로 진행을 하면 결과적으로 정답 배열에는 각 노드별 부모 노드의 번호가 저장되게 된다.

 

주의 !!

처음에는 각각 노드별로 bfs를 그 때마다 돌리려고 했는데 그렇게 된다면 최악의 경우 N* bfs 시간초과를 피하기 힘드니 미리 bfs를 돌려서 정답배열을 만드는 방법으로 해결하자!

• bfs -> O(N+E)
• 2->N까지 탐색 -> O(N)

각각 실행 시 최대 O(V+E)지만 탐색하면서 BFS를 함께 실행시 O(N * (N+E))의 시간복잡도가 걸리게 된다.

import sys
from collections import deque

# sys.stdin = open("input.txt")
input = sys.stdin.readline
nodes = int(input())

graph = [[] for _ in range(nodes+1)]

#-- 양방향 그래프 연결
for _ in range(nodes-1):
    nodeA, nodeB = map(int, input().split())
    graph[nodeA].append(nodeB)
    graph[nodeB].append(nodeA)

#-- 부모노드에 대한 정보를 저장할 정답 배열 선언
answer = [0] * (nodes+1)

#-- BFS탐색
def bfs():
    visit = [False] * (nodes+1)
    queue = deque()
    queue.append(1)
    visit[1] = True
    #-- 루트 노드인 1번부터 시작
    
    while queue:
        node = queue.popleft()
        #-- 노드에 연결된 모든 노드들을 탐색
        for data in graph[node]:
            #-- 최초 방문이라면 해당 데이터의 부모는 현재 기준으로 삼고 있는 노드
            if visit[data] == False:
                answer[data] = node
                visit[data] = True
                queue.append(data)

#-- BFS 실행
bfs()
#-- 정답 출력
for target in range(2, (nodes+1)):
    print(answer[target])