BFS와 DFS

이것이 코딩테스트다 교재를 기반으로 학습하고 정리한 내용입니다.

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀	큐 자료구조

---

DFS

그래프의 깊은 부분을 우선저긍로 탐색하는 알고리즘으로 최대한 멀리 있는 노드를 우선으로 탐색

 

DFS의 동작 과정

DFS는 스택 자료구조를 활용하고, 재귀를 통해 구현할 수 있다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리한다. 이때 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 재귀함수를 통해서 2번과정이 불가할때 까지 반복

---

BFS

가까운 노드부터 탐색하는 알고리즘

 

BFS의 동작 과정

큐 자료구조를 활용해서 구현할 수 있다.

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

 

---

예제문제

미로탈출.py _ DFS방식으로 풀이

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

def dfs(x,y):
    #상하좌우 확인
    for i in range(4):
        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 #최단 경로로 최신화하면서 진행
            dfs(nx,ny) # 다음 경로에 대한 노드 이동
    return graph[n-1][m-1] # n x m이 미로의 탈출구이기 때문에 위 방식으로 진행하면 [n-1][m-1]의 값이 최단 경로 값이다.

# 시작위치가 (1,1) 이라고 했으니, 리스트 특성상 (0,0) 부터 시작된다.
print(dfs(0,0))

 

미로탈출.py _ BFS방식으로 풀이

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]

def bfs(x,y):
    # bfs구현을 위한 큐 선언
    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 < 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]

print(bfs(0,0))