[알고리즘] DFS/BFS 알고리즘 (그래프 탐색 알고리즘)

* 그래프 탐색 알고리즘 (DFS/BFS)

- 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

-> DFS / BFS

 

* DFS (Depth-First-Search)

: 깊이 우선 탐색

-> 깊은 부분을 우선적으로 탐색하는 알고리즘

**** 스택 자료구조(혹은 재귀 함수)를 이용 ****

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

- 전체 노드의 탐색 순서 = 스택에 들어간 순서

[DFS 소스코드 예제]

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]
]

# 모든 노드가 아직 방문 X, index[0]은 사용하지 않기 때문에 길이+1해 줌
visited = [False]*9

dfs(graph, 1, visited)

 

* BFS (Breadth-First-Search)

: 너비 우선 탐색

-> 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

**** 큐 자료구조를 이용 ****

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

- 특정 조건에서의 최단경로 해결 문제

 

[BFS 소스코드 예제]

from collections import deque

def bfs(graph, start, visited):
    # 시작 노드를 큐에 넣어준다
    queue = deque([start])
    # 시작 노드를 방문한 것으로 처리
    visited[start] = True
    # 큐가 비어있을 때까지 (queue = False 이면 while문 중단)
    while queue:
        # 시작 노드를 큐에서 제거 후 출력
        v = queue.popleft()
        print(v, end=' ')

        # 시작 노드와 연결된 노드들부터 방문
        for i in graph[v]:
            # 이미 방문을 했다면 True -> not True = False => if문 실행 X
            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]
]

# 모든 노드가 아직 방문 X, index[0]은 사용하지 않기 때문에 길이+1해 줌
visited = [False]*9

bfs(graph, 1, visited)

---

[대표 예제 1] 음료수 얼려 먹기

by DFS
1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있음
3. 모든 노드에 대하여 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트

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
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False

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

graph = []
for i in range(N):
    graph.append(list(map(int,input())))

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

 

[대표 예제 2] 미로 탈출

by BFS
- 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색

def bfs(x,y):
    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()
        for i in range():
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >=n or ny < 0 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]

from collections import deque

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

graph = []
for i in range(n):
    graph.append(list(map(int,input())))

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

print(bfs(0,0))

---

강의 내용 출처 - https://youtu.be/7C9RgOcvkvo

(이코테 2021 강의 몰아보기) 3. DFS & BFS