[Algorithm] 탐색 알고리즘 DFS, BFS

# 그래프의 기본 구조

: 노드Node와 간선Edge로 표현되며 이때 노드를 정점Vertex라고도 말한다.

그래프를 표현하는 방식

1. 인접행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결관계 표현
2. 인접리스트(Adjacency List): 리스트로 그래프의 연결관계 표현

 

인접행렬Adjacency Matrix

INF = 1e7 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

인접리스트(Adjacency List)

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장
graph[0].append((1,7))
graph[0].append((2,5))

# 노드 1에 연결된 노드 정보 저장
graph[1].append((0,7))

# 노드 2에 연결된 노드 정보 저장
graph[2].append((0,5))

print(graph)

인접행렬 vs 인접리스트

• 인접행렬 장점: 인접리스트에 비해 두 연결 노드가 연결되어 있는지에 대한 정보 얻는 속도 빠름
• 인접리스트 장점: 인접행렬에 비해 연결된 정보만을 저장하기 때문에 메모리가 효율적으로 사용

---

# DFS

Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

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

방문처리: 스택에 한 번 삽입되어 처리된 코드가 다시 삽입되지 않게 체크하는 것을 의미

ex.

 

노드의 탐색 순서는 아래와 같다.

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

시간 복잡도는 $O(N)$이다.

 

DFS는 스택을 이용하는 알고리즘이기 때문에, 실제 구현은 재귀 함수를 이용했을 때 간결하게 구현 가능하다.

# DFS Method
def dfs(graph, v, visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 반복
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    
# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 호출
dfs(graph, 1, visited)

---

# BFS

Breadth-First Search, 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘

최대한 멀리 있는 노드를 우선적으로 탐색하는 DFS와 반대이다.

 

BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.

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

 

같은 예시로 진행 방법을 알아보자.

 

노드 탐색 순서(큐에 들어간 순서)

1-> 2-> 3-> 8-> 7-> 4-> 5-> 6

 

시간 복잡도는 $O(N)$이다.

 

DFS는 큐를 이용하는 알고리즘이고, deque 라이브러리를 사용하는 것이 좋다.

그리고 일반적인 실제 수행 시간은 DFS보다 좋은 편이다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False]*9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

---

DFS vs BFS

 

DFS
1) 연결된 그래프를 완전 탐색하는데 활용가능
2) 모든 경우를 하나하나 다 탐색을 해야될경우 이용(위의 예의 경우 조합, 순열 모든 경우의수를 하나한 다 찾고자할때)
3) 위의 개념과 결부된 깊이 우선탐색이라는 개념을 가진 순열, 조합 구현에 활용

BFS
1) DFS와 마찬가지로 연결된 그래프를 완전탐색하는데 활용
2) depth(깊이)를 계산해야되는 문제에 활용(위의 문제예의 경우 최단경로의 길이 == depth(깊이))
3) 위의 개념과 결부된 가중치가 같은 그래프에서 최단거리를 찾는데 활용

(출처: https://foameraserblue.tistory.com/188?category=481823)

 

---

https://www.youtube.com/watch?v=BsYbdUnKZ-Y

 

---

# 예제 문제

이 문제는 dfs로 접근 가능하다.

알고리즘

1. 특정한 지점의 주변 상/하/좌/우를 살펴본 뒤 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문

2. 방문한 지점에서 다시 상/하/좌/우 살펴보면서 방문을 다시 진행하면  > 연결된 모든 지점 방문 가능

3. 1&2번 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수 세기

💡
위에서 배운 것처럼 visited 배열을 굳이 만들지 않고도
0: 방문 안함
1: 방문 함
이렇게 값으로 처리해버릴 수도 있다

 

import sys
sys.stdin = open("input.txt", "r")

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# dfs로 특정 노드 방문 후에 재귀적 방법으로 해결
def dfs(x,y):
    # 주어진 범위를 넘어가는 경우 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
     
    if graph[x][y] == 0:
        graph[x][y] = 1
        for i in range(4):
            dfs(x + dx[i], y + dy[i])
        return True
    return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            result += 1
print(result)

 

'최소' > 이런 얘기가 나왔다면 bfs로 푸는 것이 좋다

(1,1)에서 출발하여 '1'의 길만을 쫓아가 (N,M)으로 가는 방법이다.

💡
visited 배열을 굳이 만들지 않고도
1의 길을 방문할 때마다 값을 올려서 가면 최단거리를 바로 구할 수 있다.
(visited 배열도 필요 없고, 최단 경로 변수도 만들 필요 없는 것)

import sys
from collections import deque
sys.stdin = open("input.txt", "r")

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]

# 이동할 네 방향 정의 (상하좌우우)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# BFS 소스코드
def bfs(x,y):  
    queue = deque()
    queue.append((x,y))

    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        # 현재 방향에서 네 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어나는 경우 무시
            if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
                continue
            # 괴물 있는 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환환    
    return graph[n-1][m-1]

# BFS를 수행한 결과 출력
print(bfs(0,0))

 

 

좌표로 주어진 경우에는 visited 배열을 사용하지 않고 코드를 짤 수가 있구나....