DFS vs BFS 고르기

박수련·2024년 1월 11일

코딩테스트 풀이 기록

목록 보기

2/6

항상 코테 문제를 풀 때 DFS, BFS 중 뭘 써야 효율적인 코드인지 해답을 찾기 어려웠다.

게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844
미로가 2차원 그래프(0 또는 1)로 주어져있고 시작점 (0,0)으로부터 도착점 (n-1, m-1)까지의 최단거리를 구하는 문제다.

이 문제에서 DFS로 풀려다가 해답이 나오지 않아 결국 BFS로 풀었다. 과연 이 문제를 어떻게 하면 DFS로 풀 수 있을까.

BFS 풀이

from collections import deque

def solution(maps):
    answer = -1
    n=len(maps)
    m=len(maps[0])
    
    visit=[[0]*m for _ in range(n)]
    
    queue=deque([(0,0,1)])
    while queue:
        x,y,cnt=queue.popleft()
        
        if x==n-1 and y==m-1:
            answer = cnt
            break
        
        for a,b in [(x,y-1),(x,y+1),(x-1,y),(x+1,y)]:
            if a>=0 and a<n and b>=0 and b<m:
                if maps[a][b]==1 and visit[a][b]==0:
                    visit[a][b]=1
                    queue.append((a,b,cnt+1))
            
    
    return answer

DFS 풀이

이 문제에서 DFS를 사용하기 위해서는 백트랙킹을 이용해야 했다.
경로1을 탐색하고 있었다면 visit[x][y] = 1로 업데이트하고 탐색이 끝난 후에는 다시 visit[x][y] = 0으로 방문 여부를 초기화 해주었다.

def solution(maps):
    answer = -1
    n = len(maps)
    m = len(maps[0])

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

    def dfs(x, y, cnt):
        nonlocal answer

        if x == n - 1 and y == m - 1:
            answer = cnt
            return

        visit[x][y] = 1

        for a, b in [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]:
            if a >= 0 and a < n and b >= 0 and b < m:
                if maps[a][b] == 1 and visit[a][b] == 0:
                    dfs(a, b, cnt + 1)

        visit[x][y] = 0		# 백트래킹

    dfs(0, 0, 1)

    return answer

하지만 이 문제에는 다음과 같은 이유로 BFS로 푸는 방법이 더 적합하였다.

DFS, BFS에 적합한 문제 유형

1. 최단 경로 탐색

BFS는 최단 경로를 탐색하는데 효과적이라고 한다.
예를 들면 미로에서 출발지로부터 도착지까지의 최단 경로를 찾는 문제에 적합하다.

DFS는 깊이를 우선적으로 탐색하기 때문에 목적지까지 도달하는 모든 경로를 찾고 그중에서 최단 거리를 가지는 경로를 찾는다.

반면 BFS는 시작 지점에서부터 차례대로 인접한 노드를 탐색하며 목적지에 도달하는 경로 중 가장 먼저 도착한 경로를 반환한다. 모든 경로를 탐색하지 않으면서 가장 빨리 목적지에 도착하는 경로를 찾을 수 있어 최단 경로 탐색에 효율적이다.

2. 깊이 우선 탐색

그래프에서 사이클을 찾는 문제( 백준 바이러스 ) 또는 모든 가능한 경로를 찾는 문제에는 DFS가 적합하다.

3. 공간 복잡도

BFS는 큐를 사용하여 탐색을 수행하기 때문에 메모리 제한이 있는 문제에서는 DFS가 유리할 수 있다.

피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946
현재 피로도 k
던전은 최소 1개, 최대 8개
던전을 탐험하기 위해서는 현재 피로도가 최소 필요 피로도보다 같거나 커야하고,
탐험 후에는 현재 피로도에서 소모 피로도가 소모된다.
던전을 최대한 많이 탐험할 수 있도록 탐험할 던전을 선택하는 문제다.

이 문제는 왜 DFS가 적합할까.
일단 주어진 모든 노드를 거쳐야 한다.
... to be continued

def dfs(k, cnt, dungeons, visited):
    global answer
    if cnt > answer:
        answer = cnt

    for i in range(len(dungeons)):
        if not visited[i] and k >= dungeons[i][0]:
            visited[i] = True
            dfs(k - dungeons[i][1], cnt + 1, dungeons, visited)
            visited[i] = False # 백트랙킹

def solution(k, dungeons):
    global answer
		answer = 0

    visited = [False] * len(dungeons)
    dfs(k, 0, dungeons, visited)
    return answer