[코테] DFS vs BFS

선택지

1. DFS or BFS 어떤것이든 사용해도 무관한 경우

2. DFS를 사용하는것이 압도적으로 편한경우

• 순열 & 조합 구현 (숫자 배열이 주어진 경우 +, - 결과값이 타겟과 일치하는 경우의 수)

  https://school.programmers.co.kr/learn/courses/30/lessons/43165

    # 프로그래머스 타겟넘버
    def solution(numbers, target):
        global count 
        count = 0
        n = len(numbers)
  
        def dfs(i, total):
            global count
            if i == len(numbers): # 모든 숫자를 다 활용했는지
                if target == total: # 타겟 숫자와 동일한지
                    count += 1
                return # 활용했지만 타겟과 동일하지 않는 경우 그냥 리턴
  
            dfs(i+1, total+numbers[i])
            dfs(i+1, total-numbers[i])
  
        dfs(0, 0)
        return count
  

• 연결된 그래프를 완전히 탐색해야 할 때 (주어진 모든 비행기 티켓을 사용해야하는 것이 문제의 조건)

  • BFS를 사용하면 첫 경로에서 갈 곳이 없는 경우 예외 케이스를 처리해주기 번거롭다

    https://school.programmers.co.kr/learn/courses/30/lessons/43164

  •   from collections import defaultdict
    
      def solution(tickets):
          graph = defaultdict(list)
    
          for (start, end) in tickets:
              graph[start].append(end)
    
          for airport in graph:
              graph[airport].sort(reverse=True)
    
          path = []
          stack = ["ICN"]
          while stack:
              route = stack[-1]
              if not graph[route]:
                  path.append(stack.pop())
              else:
                  next_route = graph[route].pop()
                  stack.append(next_route)
    
          return path[::-1]
    

3. BFS를 사용하는것이 압도적으로 편한경우

• 최단 경로 탐색 (2차원 배열에서 벽을 피해 목적지에 갈 수 있는 거리의 최단)

  https://school.programmers.co.kr/learn/courses/30/lessons/1844

    # 프로그래머스 게임 맵 최단거리
    from collections import deque
  
    def solution(maps):
        # 상하좌우
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
  
        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 < 0 or ny < 0 or nx >= n or ny >= m: # 좌표 범위 벗어난 경우
                        continue
                    if maps[nx][ny] == 0: # 벽인 경우
                        continue
                    if maps[nx][ny] == 1: # 옮겨갈 수 있는 경우
                        queue.append((nx, ny))
                        maps[nx][ny] = maps[x][y] + 1
  
        min_count = int(1e9)
        n, m = len(maps), len(maps[0])
  
        bfs(0, 0)
        answer = maps[n-1][m-1] if maps[n-1][m-1] != 1 else -1   
  
        return answer
  

  • BFS는 시작 지점에서 가까운 정점부터 차례대로 탐색해 나가기 때문에 최단 거리를 먼저 찾을 수 있다. BFS는 탐색 과정에서 방문한 정점을 큐에 저장하여 FIFO 방식으로 탐색하므로, 목적지에 먼저 도착한 경우에는 그 때의 거리가 최단 거리가 된다.

    반면에 DFS는 스택 또는 재귀를 사용하여 깊이를 우선적으로 탐색하므로, 경로를 따라 최종 목적지까지 도달할 때까지 탐색을 진행한다. 따라서 최단 거리를 보장하지 않으며, 경우에 따라 모든 경로를 탐색한 후에야 최단 거리를 찾을 수 있다. 따라서, 최단 거리 문제에는 BFS가 훨씬 효율적이다.