[BOJ]1725:ツリーの親を検索する

🔒 例

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

4
6
1
3
1
4

>> 12
>> 1 2
>> 1 3
>> 2 4
>> 3 5
>> 3 6
>> 4 7
>> 4 8
>> 5 9
>> 5 10
>> 6 11
>> 6 12

1
1
2
3
3
4
4
5
5
6
6

🔧 に答える

1. 부모-자식 관계가 아닌 간선 정보 제공 -> 무방향 그래프로 입력 저장
2. 시작점(트리의 루트)가 제공 -> 그래프 탐색을 이용하여 부모 찾기
	2.1 bfs(너비우선탐색) : 큐 활용
    2.2 dfs(깊이우선탐색) : 스택/재귀함수를 활용

🔑 答案用紙

import sys
from collections import deque

input = sys.stdin.readline

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

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

def bfs():
    q = deque()
    # 루트 설정
    q.append(1)
    # 그래프 팀색
    while q:
        node = q.popleft()
        for i in graph[node]:
        	# 큐에 넣으려는 노드들 중 해당 노드가 부모가 없으면 부모 설정
            if parent[i] == 0:
                parent[i] = node
                q.append(i)

    return parent

bfs()
for i in parent[2:]:
    print(i)

💡 コンセプト

### 너비우선탐색(bfs)
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

	while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True