[Python] 그래프 탐색 알고리즘 - DFS 깊이우선탐색 & BFS 너비우선탐색

그래프 Graph

정점(node, vertex)들의 연결 관계를 간선(edge)을 이용하여 표현한 자료구조.

1. (정점 개수 v) * (정점 개수 v) 크기 의 인접 행렬로 구현하는 방법과
2. 각 정점에 연결된 다른 정점들을 인접 리스트로 표현하여 구현하는 방법이 주로 사용된다.

인접 행렬로 구현 - 각 노드에 대해 인접한 노드 정보를 각각 행렬에 표시

인접 리스트로 구현 - 각 노드에 대해 인접한 노드의 정보를 배열로 저장 (보통 인덱스 0번은 비워둠)

그래프에 저장된 데이터를 조회하는 알고리즘으로 DFS 깊이우선탐색 알고리즘과 BFS 너비우선탐색 알고리즘이 있다. 

✅ 그래프 탐색의 rule
- 노드마다 정확히 한 번씩만 탐색한다. (중복 탐색 X)
- 노드에 방문 표시를 해가면서 탐색하되, 연결된 노드는 전부 탐색할 수 있도록 한다.

 

DFS 깊이우선탐색 (Depth-First Search)

스택 자료구조(or 재귀함수)를 사용해서 재귀적으로 반복하며 깊은 부분을 우선적으로 탐색하는 그래프 탐색 방식
→ 시작 위치에서 탐색 조건을 만족하는 노드 중 가장 작은 값으로 재귀 함수 호출
→ 탐색 시작 노드를 스택에 삽입하고 방문 처리
→ 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
→ 연결된 노드 중 더 이상 갈 곳이 없으면 스택에서 최상단 노드를 꺼내고 호출 시점으로 return (⇒ 되돌아가기, backtrack)

• 정점 개수 v ≤ 1,000 → 인접 행렬 or 인접 리스트 중 골라서 해결
• 정점 개수 v ≤ 100,000 → 항상 인접 리스트로 해결

알고리즘 세부 동작 과정

DFS, 시작점: a, 방문 기준: 알파벳 순

1. 노드 a부터 탐색 시작
현재 스택 : [a]
방문 순서 : a

2. 스택의 최상단 노드 a의 인접 노드 b, c 중 b부터 탐색
현재 스택 : [a, b]
방문 순서 : a b

3. 스택의 최상단 노드 b의 인접 노드 d, e 중 d부터 탐색
현재 스택 : [a, b, d]
방문 순서 : a b d

4. 스택의 최상단 노드 d의 인접 노드 g를 탐색
현재 스택 : [a, b, d, g]
방문 순서 : a b d g

5. 스택의 최상단 노드 g에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a, b, d]
방문 순서 : a b d g

6. 스택의 최상단 노드 d에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a, b]
방문 순서 : a b d g

7. 스택의 최상단 노드 b의 인접 노드 d, e 중 방문하지 않은 e를 탐색
현재 스택 : [a, b, e]
방문 순서 : a b d g e

8.  스택의 최상단 노드 e의 인접 노드 h, i 중 h부터 탐색
현재 스택 : [a, b, e, h]
방문 순서 : a b d g e h

9. 스택의 최상단 노드 h에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a, b, e]
방문 순서 : a b d g e h

10. 스택의 최상단 노드 e의 인접 노드 h, i 중 방문하지 않은 i 탐색
현재 스택 : [a, b, e, i]
방문 순서 : a b d g e h i

11. 스택의 최상단 노드 i에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a, b, e]
방문 순서 : a b d g e h i

12. 스택의 최상단 노드 e에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a, b]
방문 순서 : a b d g e h i

13. 스택의 최상단 노드 b에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a]
방문 순서 : a b d g e h i

14. 스택의 최상단 노드 a의 인접 노드 b, c 중 방문하지 않은 c를 탐색
현재 스택 : [a, c]
방문 순서 : a b d g e h i c

15. 스택의 최상단 노드 c의 인접 노드 f를 탐색
현재 스택 : [a, c, f]
방문 순서 : a b d g e h i c f

16. 스택의 최상단 노드 f에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a, c]
방문 순서 : a b d g e h i c f

17. 스택의 최상단 노드 c에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : [a]
방문 순서 : a b d g e h i c f

18. 스택의 최상단 노드 a에서 방문할 수 있는 인접 노드가 없으므로 pop
현재 스택 : []
방문 순서 : a b d g e h i c f

19. 스택에 더 이상 방문할 노드가 없으므로 탐색 종료
최종 방문 순서 : a b d g e h i c f

인접 리스트로 DFS 구현

# 1번 노드부터 dfs를 진행했을 때 방문할 수 있는 노드의 수를 구해보자.

n, m = tuple(map(int, input().split()))

# 그래프를 표현할 인접 리스트
arr = [
    [] for _ in range(n+1)
]

# 각 노드의 방문 여부를 기록하는 리스트 (0번 인덱스는 사용하지 않기 위해 n+1만큼 생성)
visited = [False] * (n+1)

# 초기 작업
for _ in range(m):
    x, y = tuple(map(int, input().split()))
    arr[x].append(y)
    arr[y].append(x)

root = 1
visited[root] = True


def dfs(v, count):
	""" 깊이우선탐색: 노드 v의 각 인접 노드들을 순차적으로 방문 """
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end='')
    # 현재 노드와 인접한 노드들을 재귀적으로 방문
    for curr in arr[v]:
        if not visited[curr]:
            cnt += 1
            dfs(curr)

dfs(root, 1) # 시작점, 방문 노드 수
print(cnt)

ex) 격자 상에서 DFS 탐색하는 문제

범위가 제한된 격자 상에서 이동해야 하기 때문에, 따로 인접 행렬이나 인접 리스트를 구현할 필요가 없다.

1. 격자를 벗어나지 않는 범위 내에서
2. 장애물이 없고
3. 방문한 적이 없을 때 이동한다.

# 격자 내에서 장애물을 피해 탈출 가능한 경로 존재 여부를 판별해보자.

n, m = tuple(map(int, input().split()))
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

visited = [
    [False for _ in range(m)]
    for _ in range(n)
]

def can_move(x, y):
    if (x >= n or y >= m): # 격자 범위를 벗어나는지
        return False
    return (visited[x][y] == 0) and (grid[x][y] == 1) # 이미 방문 or 장애물 여부

escape = 0

def dfs(x, y):
    global escape

    if (x, y) == (n-1, m-1): # 도착 지점
        escape = 1

    dxs, dys = [1, 0], [0, 1]
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if can_move(nx, ny):
            visited[nx][ny] = True
            dfs(nx, ny)

visited[0][0] = True
dfs(0, 0)
print(escape)

ex) DFS로 격자 범위를 구분하는 문제

# 격자 상에 구현된 지형 평면도를 여러 개의 마을로 구분해서 만들 수 있는 마을의 개수를 구해보자. 

n = int(input())
arr = [
    list(map(int, input().split()))
    for _ in range(n)
]

visited = [
    [False] * n
    for _ in range(n)
]

def can_move(x, y):
    return x >= 0 and x < n and y >= 0 and y < n and arr[x][y] and not visited[x][y]

town = []

def dfs(x, y):
    global cnt

    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if can_move(nx, ny):
            visited[nx][ny] = True
            cnt += 1
            dfs(nx, ny)

for i in range(n):
    for j in range(n):
        cnt = 0
        if arr[i][j] and not visited[i][j]:
            visited[i][j] = True
            cnt += 1
            dfs(i, j)
        if cnt != 0:
            town.append(cnt)
            
print(len(town))
for t in sorted(town):
    print(t)

BFS 너비우선탐색

큐 자료구조를 사용해서 그래프를 가까운 노드부터 우선적으로 탐색하는 방법.

재귀함수 호출 대신 시작 노드를 큐에 삽입하고 방문 처리를 한다.
→ 현재 위치를 `q.popleft()`로 설정, 인접한 노드 중 방문 가능한 모든 노드를 모두 큐에 삽입하고 방문 처리한다.
→ 이 과정을 반복하면서 조건을 만족할 때까지 이동한다.

실행시간 문제로 실제 파이썬에서는 queue보다 deque를 사용해서 구현한다.

BFS의 정의 상 가까운 위치의 노드부터 탐색하기 때문에
시작 위치로부터의 최단 거리 or 최소 이동 횟수를 구하는 문제에 활용하기 좋다.

알고리즘 세부 동작 과정

BFS, 시작점: a, 방문 기준: 알파벳 순

1. 노드 a부터 탐색 시작
현재 큐 : [a]
방문 순서 : a

2. 큐에서 노드 a를 꺼내고(현재 노드: a), 방문하지 않은 인접 노드 b, c를 모두 큐에 삽입하고 방문 처리
현재 큐 : [b, c]
방문 순서 : a

3. 큐에서 노드 b를 꺼내고(현재 노드: b), 방문하지 않은 인접 노드 d, e를 모두 큐에 삽입하고 방문 처리
현재 큐 : [c, d, e]
방문 순서 : a b

4. 큐에서 노드 c를 꺼내고(현재 노드: c), 방문하지 않은 인접 노드 f를 큐에 삽입하고 방문 처리
현재 큐 : [d, e, f]
방문 순서 : a b c

5. 큐에서 노드 d를 꺼내고(현재 노드: d), 방문하지 않은 인접 노드 g를 큐에 삽입하고 방문 처리
현재 큐 : [e, f, g]
방문 순서 : a b c d

6. 큐에서 노드 e를 꺼내고(현재 노드: e), 방문하지 않은 인접 노드 h, i를 모두 큐에 삽입하고 방문 처리
현재 큐 : [f, g, h, i]
방문 순서 : a b c d e

7. 큐에서 노드 f를 꺼내고(현재 노드: f), 방문하지 않은 인접 노드가 없으므로 무시
현재 큐 : [g, h, i]
방문 순서 : a b c d e f

8. 큐에서 노드 g를 꺼내고(현재 노드: g), 방문하지 않은 인접 노드가 없으므로 무시
현재 큐 : [h, i]
방문 순서 : a b c d e f g

9. 큐에서 노드 h를 꺼내고(현재 노드: h), 방문하지 않은 인접 노드가 없으므로 무시
현재 큐 : [i]
방문 순서 : a b c d e f g h

10. 큐에서 노드 i를 꺼내고(현재 노드: i), 방문하지 않은 인접 노드가 없으므로 무시
현재 큐 : []
방문 순서 : a b c d e f g h i

11. 큐에 더 이상 방문할 노드가 없으므로 탐색 종료
최종 방문 순서 : a b c d e f g h i

격자에서의 BFS 탐색

from collections import deque

q = deque() # 방문 정점을 관리할 큐

n, m = tuple(map(int, input().split()))
graph = [
    list(map(int, input().split()))
    for _ in range(n)
] # 탐색할 그래프 정보

visited = [
    [False] * m
    for _ in range(n)
] # 정점 방문 여부를 기록

escape = 0 # 탈출 가능 -> 1, 탈출 불가능 -> 0 

def in_range(x, y):
	""" 방문하려는 정점의 위치 정보가 주어진 격자 내 범위를 만족하는가 """
    return x >= 0 and x < n and y >= 0 and y < m

def can_move(x, y):
	""" 방문 가능한 정점의 조건을 모두 만족하는가 (범위 내 + 장애물 없음 + 아직 방문 안 함) """
    return in_range(x, y) and graph[x][y] and not visited[x][y]

def push(x, y):
	""" 방문하려는 정점의 방문 여부를 갱신하고 큐에 저장 """
    visited[x][y] = True
    q.append((x, y))

def bfs():
    global escape
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1] # 인접한 격자 위치 정보
    while q:
        x, y = q.popleft() # 현재 위치
        
        # 목적지 도착하면 성공
        if (x, y) == (n-1, m-1):
            escape = 1
            break
		
        # 상하좌우 인접한 위치 정점에 대해서 방문 가능 여부 파악 후 이동
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if can_move(nx, ny):
                push(nx, ny)

push(0, 0) # 초기 설정 (시작점 0, 0)
bfs() # 탐색 시작

print(escape) # result

ex) 가중치가 동일한 그래프에서의 탐색

# 목적지에 도착할 수 있는 가능한 이동경로의 최소 거리를 구해보자.

from collections import deque
q = deque()

n = int(input())
r1, c1, r2, c2 = tuple(map(int, input().split()))

grid = [
    [0] * n
    for _ in range(n)
]

end = (r2-1, c2-1)

visited = [
    [0] * n
    for _ in range(n)
]

def can_go(x, y):
    return x >= 0 and x < n and y >= 0 and y < n and not visited[x][y]

def push(x, y, cnt):
    visited[x][y] = True
    q.append((x, y, cnt))

def bfs():
    dxs, dys = [-1, -2, -2, -1, 1, 2, 2, 1], [-2, -1, 1, 2, 2, 1, -1, -2]

    while q:
        x, y, cnt = q.popleft()
        if (x, y) == end:
            return cnt # 가능한 경로 중 가장 빨리 도착한 최소 경로의 이동 거리 반환
        
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if can_go(nx, ny):
                push(nx, ny, cnt+1) # 한 번 이동할 때마다 +1
        
    return -1


push(r1-1, c1-1, 0)
move_cnt = bfs()
print(move_cnt)