[알고리즘] 1260 python DFS & BFS

1260: DFS와 BFS

solved.ac 에서 Silver 2에 있다.
알고리즘 강의에서 수도코드로는 많이 봤는데 실제 코드로 구현한 기억이 없어서 간단하게 해보기로 하였다.

---

DFS 는 Depth First, BFS 는 Breadth First의 약자로,
간단히 말해 DFS는 한 방향으로 리프까지 찍고 오는 것, BFS는 가까운 노드를 모두 방문한 후에 먼 노드를 방문하는 것으로 생각하면 편하다.

---

from collections import deque
import numpy as np

N, M, V = map(int, input().split())

G = np.zeros((N+1, N+1), dtype=int)
visit = np.zeros(N+1, dtype=int)

for i in range(M):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1

def dfs(v):
    visit[v] = 1
    print(v, end = ' ')
    for i in range(1, N+1):
        if visit[i] == 0 and G[v][i] == 1:
            dfs(i)

def bfs(v):
    que = deque()
    que.append(v)
    visit[v] = 1
    while que:
        v = que.popleft()
        print(v, end = ' ')
        for i in range(1, N+1):
            if visit[i] == 0 and G[v][i] == 1:
                que.append(i)
                visit[i] = 1
                
dfs(V)
visit = np.zeros(N+1, dtype=int)
print()
bfs(V)

먼저 그래프의 인접행렬 G 를 만들고 경로를 입력받아 인접행렬의 해당 값을 1로 변경한다.

함수 dfs는 특정 노드 v 를 인자로 전달받아 탐색 여부를 저장하고 다른 모든 노드에 대해
탐색된 적이 없고 v 에서 경로가 존재할 경우 해당 노드에 대해 dfs 함수를 재귀적으로 호출한다.

함수 bfs는 deque 를 큐로 사용하여, v 가 인자로 전달되었을 때 탐색 여부를 저장하고 큐에 push한다.
큐에 저장된 노드가 모두 pop될 때까지, 큐에 있는 노드와 인접해있고 탐색된 적이 없는 노드를 큐에 push하는 작업을 반복한다.

---

이번에는 단순히 출력만을 수행했지만, 탐색될 때 다른 작업이 필요하다면

print(v, end = ' ')

에 추가로 삽입할 수 있겠다.

참고로 위의 코드는 제출 시 런타임 에러가 뜨는데, Numpy가 파이썬 표준 라이브러리가 아니라 그런 것으로 보인다.
Numpy배열이 list보다 연산이 빨라서 사용했는데

G = [[0]* (N+1) for i in range(N+1)]
visit = [0]* (N+1)

로 바꿀 필요가 있었다.