[백준/Python] 1260번: DFS와 BFS

문제

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

1260번: DFS와 BFS

---

문제 요약

N개의 정점과 정점을 잇는 M개의 간선으로 이루어진 그래프를 입력 받고, 그래프를 V번 정점부터 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력한다.

 

+ 정점 번호는 1번부터 N까지 존재한다.

+ 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.

---

코드

from collections import deque

def dfs(num):
    for n_num in graph[num]:
        if check[n_num] == 0: # 아직 탐색하지 않은 친구라면
            check[n_num] = 1
            d_res.append(n_num)
            dfs(n_num)

def bfs(num):
    que = deque()
    que.append(num) # 시작 노드 번호를 미리 큐에 저장
    check[num] = 1

    while que:
        n_num = que.popleft()
        b_res.append(n_num)
        for i in graph[n_num]: # 해당 노드와 인접한 노드 번호 중
            if check[i] == 0: # 방문하지 않은 노드라면
                check[i] = 1
                que.append(i)
        

N, M, V = map(int, input().split())
# N은 정점 개수, M은 간선의 개수, V는 탐색을 시작할 정점 번호

graph = [[] for _ in range(N + 1)] 
# 정점 번호가 1번부터 N번까지 이므로 N + 1 크기의 인접 리스트 생성 (인덱스 0은 사용 X)

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

# 방문 가능한 정점이 여러 개라면 작은 번호를 먼저 방문 => 인접리스트를 오름차순 정렬
for i in range(N + 1):
    graph[i] = sorted(graph[i])

# 이전 탐색에서 방문했는지를 체크하는 배열 (방문: 0, 방문 X: 1)
check = [0] * (N + 1)

d_res = [] # DFS 탐색 순으로 노드 번호 저장
b_res = [] # BFS 탐색 순으로 노드 번호 저장

check[V] = 1 # 방문 표시 체크 
d_res.append(V)
dfs(V) # V번 정점부터 dfs 탐색

check = [0] * (N + 1) # 다시 bfs 탐색도 해야하므로 check 초기화
bfs(V) # V번 정점부터 bfs 탐색

print(*d_res)
print(*b_res)

---

코드 설명

1. a번 노드와 b번 노드를 잇는 간선을 입력 받고 인접 리스트에 추가한다.

+ 방문 가능한 정점이 여러 개라면 작은 번호를 먼저 방문해야 하므로 인접 리스트를 오름차순 정렬한다.

 

2. dfs, bfs 함수를 통해 V번 노드부터 DFS, BFS를 진행하고 방문한 노드 번호를 배열에 담아 출력한다.