[ 알고리즘 ] DFS, BFS 란?

그래프를 탐색하는 방법은 총 두 가지가 있다.

그래프를 탐색한다는 개념은? 정점(node)와 간선(edge)로 이루어진 그래프에서 모든 정점들을 한 번씩 방문하는 것을 뜻한다.

 

DFS (Depth-First Search)  :  깊이 우선 탐색

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

• 스택(Stack)이나 재귀함수를  이용해서 알고리즘을 풀 수 있다. 주로 재귀함수를 사용하여 짧게 코드를 작성할 수 있다.
• 모든 가능한 해를 탐색해야 할 때: DFS는 가능한 모든 경로를 깊게 탐색하면서 해를 찾는다. 따라서 모든 가능한 해를 찾거나, 해가 될 수 있는 모든 조합을 시도해봐야 하는 문제(예: 백트래킹 문제)에 적합하다.
• 최대 깊이가 제한적일 때: 깊이가 제한적이거나 깊이의 최대치가 그리 크지 않은 경우, DFS는 효율적으로 작동할 수 있다.
• 경로의 발견이 중요할 때: 시작점에서 특정 노드까지의 경로를 찾거나, 두 노드 사이의 경로가 존재하는지 확인해야 할 때 유용하다.

BFS (Breadth-First Search)  :  너비 우선탐색

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점부터 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

• 큐(Queue)를  이용해서 알고리즘을 풀 수 있다.
• 최단 경로를 찾아야 할 때: BFS는 시작점에서 각 노드까지의 최단 경로를 찾을 때 유용하다. 특히 가중치가 없는 그래프에서의 최단 경로를 찾을 때 많이 사용된다.
• 트리나 그래프의 레벨별 정보가 필요할 때: BFS는 레벨별로 탐색을 진행하기 때문에, 각 레벨에 대한 정보가 필요할 때 적합하다.
• 최소 비용 문제: 각 단계에서 가능한 모든 선택지를 고려하면서, 최소 비용이나 최소 단계 수를 요구하는 문제에 BFS가 적합할 수 있다.

 

DFS 문제 )

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

DFS 코드 )

def solution(numbers, target):
    answer = 0  # 타겟 넘버를 만드는 방법의 수
    
    def dfs(index, total):
        nonlocal answer  # 외부 스코프의 answer 변수를 사용하기 위해 nonlocal 키워드 사용
        if index == len(numbers):  # 모든 숫자를 다 사용했을 때
            if total == target:  # 현재까지의 합계가 타겟 넘버와 같다면
                answer += 1  # 방법의 수를 1 증가
            return
        
        # 현재 숫자를 더하는 경우
        dfs(index + 1, total + numbers[index])
        # 현재 숫자를 빼는 경우
        dfs(index + 1, total - numbers[index])
        
    # DFS 탐색 시작
    dfs(0, 0)
    
    return answer

• dfs 함수 내에서 nonlocal 말고 solution 함수 내에서 global로 선언해도 된다.
• dfs 탐색 과정
  if index == n: 모든 숫자를 탐색했을 때, index가 numbers의 길이와 같아지면, 현재까지의 합(total)이 타겟 넘버와 동일한지 확인한다.
  if total == target: 현재 합계가 타겟 넘버와 같다면, answer를 1 증가시켜 조합의 수를 하나 늘린다.
  이후, 현재 숫자(numbers[index])를 더하거나 빼는 두 가지 경우를 모두 탐색하기 위해 dfs 함수를 재귀적으로 호출합니다.
• dfs(0, 0): index와 total을 0으로 초기화하면서 DFS 탐색을 시작한다. 이는 아직 어떤 숫자도 선택하지 않았고, 합계도 0임을 의미한다.

 

 

BFS 문제 )

다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

 

비어있는 칸, 즉 갈 수 있는 길이 1로 표시되어 있음. 갈 수 없으면 0.

 

BFS 코드 )

from collections import deque

def solution(maps):
    n = len(maps)  # 행의 길이
    m = len(maps[0])  # 열의 길이
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 동, 남, 서, 북 이동 방향
    
    # BFS를 위한 큐 생성 및 초기 위치 삽입
    queue = deque([(0, 0, 1)])  # (행, 열, 거리)
    while queue:
        x, y, dist = queue.popleft()
        
        # 목적지에 도달했을 경우 거리 반환
        if x == n-1 and y == m-1:
            return dist
        
        # 현재 위치에서 4가지 방향으로 이동
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 이동 가능한 위치인지 확인
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                maps[nx][ny] = 0  # 방문 처리 (중복 방문 방지)
                queue.append((nx, ny, dist+1))
                
    return -1  # 목적지에 도달할 수 없는 경우

 

queue 리스트에 아직 항목이 남아 있는 동안 반복문을 실행하라는 의미.

for 문 안의 if 문은 현재 위치에서 nx, ny로 이동할 수 있는지 확인하는 것. 이동할 위치인 nx, ny가 게임 맵 안에 위치하고 있는지와 갈 수 있는 칸이면 그 칸으로 이동하며, 중복 방문할 수 없도록 1에서 0으로 바꿔버리며, 현재 위치인 nx, ny와 이동한 칸수(=거리)를 새롭게 큐에 넣는다.