(python) 11725번 트리의 부모 찾기

문제 

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

11725번: 트리의 부모 찾기

트리의 루트를 1로 정했을 때 각 노드의 부모를 구하는 프로그램

 

여기서 트리 구조를 알아야 하는데

자료구조에서의 트리는 부모 - 자식 관계로 정의하고 부모에서 자식으로 간선이 이어져 있는 그래프

 

루트 노드 : 트리에서 부모가 없는 최상위 노드, 시작점 여기서 루트는 1

부모 노드 : 루트 노드 방향으로 직접 연결된 노드  여기서 4의 부모 노드는 1이다.

자식 노드 : 루트 노드 반대방향으로 직접 연결된 노드 여기서 4의 자식 노드는 2, 7이다.

형제 노드 : 같은 부모 노드를 갖는 노드들 여기서 2, 7은 4를 부모 노드로 둬 형제 노드다.

 

암튼 문제에서 각 노드별 부모 노드를 출력시키면 된다.

 

입력

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

4 2 이렇게 주어지면 2번 노드와 4번 노드가 선으로 연결되어 있다는 뜻이다.

 

출력

루트인 1을 제외하고 부모노드를 순서대로 출력하면 된다.

즉 2번 노드의 부모부터 N번 노드의 부모까지 출력

 

풀이

트리 문제처럼 생겼지만 BFS를 이용하여 푼다.

노드 상의 BFS는 시작점에서 연결되어있는 모든 수를 큐에 넣기 때문에

시작점을 부모로 두고 있는 모든 자식 노드를 알 수 있다.

 

이중 리스트에 각 노드에 연결되어있는 노드를 넣어주고

방문 처리를 하기 위한 리스트를 만들어주고

BFS를 사용하여 연결되어있는 노드가

1. 루트인 1번 노드가 아닌 노드

2. 방문한 노드는 부모노드이기 때문에 방문하지 않은 노드

위 경우일 때  방문 처리용 리스트에 부모노드를 입력해 준다.

 

코드

from collections import deque # 큐
import sys # 입력 빠르게 하기 위해

def bfs(root, v, tree):
  queue = deque([v]) # 시작 위치 넣어주고
  while queue:
    x = queue.popleft() # 큐에서 꺼냄
    for i in root[x]: # 해당 노드에 연결된 노드
      if tree[i] == 0 and i != 1: # 방문하지 않았거나 1번 노드가 아닐 경우
        queue.append(i) # 큐에 추가
        tree[i] = x # 연결된 노드 번호에 큐에서 꺼낸 노드번호(부모) 넣기
n = int(input())
root = [[] for _ in range(n + 1)] 
tree = [0] * (n + 1) # 방문처리용 리스트
for i in range(n - 1):
  f, s = map(int, sys.stdin.readline().split())
  root[f].append(s) # 입력받은 노드 간선을 리스트에 저장
  root[s].append(f)
bfs(root, 1, tree)
for i in range(2, n + 1):
  print(tree[i])

 

BFS 문제이지만 트리 구조에 대한 지식이 있어야 풀 수 있는 문제로 트리 용어 숙지가 필요