[백준] 11725 트리의 부모 찾기

[백준] 11725 트리의 부모 찾기

dfs&bfs / 파이썬

 

 

[문제]

 

 

bfs나 dfs를 사용하는 문제

 

 

입력값) n:노드 a,b: 연결된 두 노드

인접 리스트방식으로 입력값이 주어짐. 백준은 이런형태가 많은 듯 하다.

 

 

 

 

[과정]

1. 기본적인 dfs탐색
2. 부모-자식노드를 저장할 딕셔너리(parent)를 생성하고 bfs를 돌때 마지막부분에 부모-자식노드를 연결

 

 

 

[소스코드]

 

# 트리의 부모 찾기

from collections import deque

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

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

parent = {}
def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    
    while q:
        v = q.popleft()    # v: 부모노드
        for i in graph[v]:    # i: 자식노드 (v의 연결된 노드이기 때문)
            if not visited[i]:
                q.append(i)
                parent[i] = v
                visited[i] = True
bfs(graph, 1, visited)

for i in range(2,n+1):
    print(parent[i])

 

나는 bfs를 사용했다.

bfs가 dfs보다 속도면에서 빠르기 때문이다.

파이썬은 웬만하면 코테에서는 bfs를 쓰는게 효율적이다.

 

 

 

---

 

 

[통과]

 

기본적인 dfs/ bfs 문제