[알고리즘/BFS & DFS] 11725번 : 트리의 부모 찾기 - python

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

11725번: 트리의 부모 찾기

 

---

• 문제
• 소요시간: 10분 7초

---

• 설계하기(접근방법) 

1. 입력받기

노드와 간선을 입력받는다

 

2. 구현하기

1부터 노드를 bfs로 순회하면서

자식 노드 번호에 부모 노드 번호를 저장한다

 

 

3. 출력하기

2번 노드부터 부모 노드를 출력한다

 

---

• 코드(출력)

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0 for _ in range(n + 1)]

for _ in range(n-1):
    p, c = map(int, input().split())
    graph[p].append(c)
    graph[c].append(p)

def bfs(start):
    q = deque()
    visited[start] = -1
    q.append(start)
    while q:
        x = q.popleft()
        for i in graph[x]:
            if visited[i] == 0:
                visited[i] = x
                q.append(i)
bfs(1)

for i in visited[2:]:
    print(i)

---

• 얻어갈 부분

1. 이전의 트리의 지름 문제보다 많이 쉬웠다. 방문한 노드의 전 노드를 저장하면 되는 문제다.