💡개요

이 포스트에서는 그래프의 기본적인 명칭 예를들면 노드, 간선 과 같은 내용은 생략한다. 또한 그래프의 구현 방법인 인접행렬과 인접리스트 방식 또한 생략한다.
또한 아래에서 나오는 예시 (문제 풀이 제외)의 그래프 구현 방법은 인접행렬 방식을 사용한다.

👁‍🗨그래프 탐색

깊이 우선 탐색

깊이 우선 탐색은 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색의 구현 방법으로는 스택을 사용하는 방법과 재귀를 사용하는 방법 두가지가 있다.

DFS의 매커니즘은 다음을 따른다.

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접노드를 스택에 넣고 방문 처리를 한다.
3. 2번 과정을 더이상 수행할 수 없을때까지 반복한다

스택을 이용한 깊이 우선 탐색

def dfs(graph, root, visited):
  stack = [root]

  while stack:
    current = stack.pop()
    print(current)
    
    if not visited[current]:
      visited[current] = 1
      stack.extend(graph[current])

재귀를 이용한 깊이 우선 탐색

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

너비 우선 탐색

너비 우선 탐색은 그래프에서 가까운 노드부터 탐색하는 탐색 기법이다.BFS를 구현할 때는 큐를 이용하여 FIFO구조를 이용한다.
파이썬에서는 큐 자료구조를 지원하는 collections 라이브러리가 존재한다.

BFS의 매커니즘은 다음과 같다
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.

코드

from collections import deque
n = int(input())
visited = [0] * n

def bfs(graph, start):
    q = deque([start])
    visited[start] = 1
    while q:
        current = q.popleft()
        for i in graph[current]:
            if not visited[i]:
                q.append(i)
                visited[i] = 1

실제 문제를 풀어볼 때에는 문제마다 선택하는 기법에 따라 문제 난이도가 달라질 수 있으니 충분히 고민해 보고 적당한 알고리즘을 고르는것이 좋다. 다양한 문제를 풀어보면서 느낀점은 DFS보다 BFS를 이용한 경우 문제 풀이가 쉬운 경우가 많았다.

예제

[BOJ-2178] - 미로 탐색

문제
문제를 요약하자면 $N\times M$ 미로가 주어졌을 때 (1, 1) 좌표에서 (N, M) 좌표로 이동하는 최소거리를 찾아라는 문제다.
그래프 탐색 알고리즘을 풀면서 느끼는 점은 DP와 상당히 유사하다는 점이다. 완전 탐색에서 시작하여 visited 노드에 중간 값을 찾아갈 수 있기 때문에 테크닉은 상당히 비슷하다는 느낌을 받았다.

from collections import deque
n, m = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

q = deque([[0, 0]])
visited[0][0] = 1
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
while q:
    cx, cy = q.popleft()
    for i in range(4):
        nx, ny = cx + dx[i], cy + dy[i]
        if 0 <= nx < n and 0 <= ny < m \
            and not visited[nx][ny] and graph[nx][ny]:
            q.append([nx, ny])
            visited[nx][ny] = visited[cx][cy] + 1

print(visited[n-1][m-1])

BFS로 구현한 미로탐색 알고리즘이다. 조건에서 갈 수 있는 길은 graph[n][m]이 1인 경우이며, 방문한 노드는 재 방문하지 않도록 처리하였다. 또한 그래프 범위를 벗어나 탐색하는 경우도 제외하였다.

그 이외의 경우 BFS 구현 규칙에 따라 큐에 저장하였으며 방문처리도 해주었다. 특히 방문 순서는 visited 배열에 이전에 있던 값보다 1 증가하면서 나중에 정답은 visited 리스트 안에 저장되도록 해주었다.