#3 Algorithm -게임 맵 최단거리 BFS로 계산하기

게임 맵 최단 경로 찾기

이번 포스트에서는 게임 맵에서 최단 경로를 찾는 문제를 해결하는 방법에 대해 자세하게 알아보려 한다. 이 문제를 해결하기 위해 BFS 알고리즘을 활용하는 방법과 함께 BFS와 DFS의 차이점에 대해서도 설명한다.

문제보러가기

문제 설명

게임 맵은 5x5 크기의 2차원 배열로 주어지며, 각 칸은 벽(0) 또는 길(1)로 이루어져 있다. 플레이어는 좌측 상단(1,1)에서 시작하여 우측 하단(5,5)로 이동해야 한다. 벽을 피해서 최단 경로를 찾는 것이 목표이다. 이동은 동, 서, 남, 북 방향으로 한 칸씩 가능하다.

BFS 알고리즘 사용 이유

BFS(Breadth-First Search)는 현재 노드와 인접한 모든 노드를 탐색한 후, 다음 깊이의 노드를 탐색하는 방법이다. 이 방식은 최단 경로를 찾기에 적합하다. 왜냐하면, 먼저 방문한 노드부터 차례로 탐색하므로, 가장 먼저 목적지에 도달한 경로가 최단 경로가 된다.

코드 설명

다음은 문제를 해결하기 위한 파이썬 코드이다. 이 코드는 BFS를 사용하여 최단 경로를 찾는다.

from collections import deque

def solution(maps):
    n = len(maps) # 행의 수
    m = len(maps[0]) # 열의 수

    # 방향 벡터 설정 (상, 하, 좌, 우)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 큐 초기화 및 시작 위치 설정
    queue = deque([(0, 0, 1)]) # (x좌표, y좌표, 이동 거리)
    maps[0][0] = 0 # 시작 위치 방문 처리

    while queue:
        x, y, dist = queue.popleft() # 현재 위치와 이동 거리 꺼내기

        if x == n - 1 and y == m - 1:
            return dist # 목적지 도착 시 이동 거리 반환

        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                queue.append((nx, ny, dist + 1)) # 새로운 위치와 이동 거리 큐에 추가
                maps[nx][ny] = 0 # 방문 처리

    return -1 # 목적지에 도착할 수 없는 경우 -1 반환

주요 로직 설명

1. 초기 설정: n과 m으로 행과 열의 수를 구하고, directions 리스트로 상하좌우 방향을 정의한다.
2. 큐 초기화: deque를 사용하여 큐를 초기화하고, 시작 위치 (0, 0, 1)를 큐에 넣는다. 시작 위치는 방문 처리한다.
3. BFS 실행: 큐가 빌 때까지 반복하며, 현재 위치와 이동 거리를 꺼내서 네 방향으로 이동 가능한지 확인한다.
4. 목적지 도착: 목적지 (n-1, m-1)에 도착하면 이동 거리를 반환한다.
5. 방문 처리: 이동 가능한 위치를 큐에 추가하고, 방문 처리한다.
6. 결과 반환: 목적지에 도달하지 못하면 -1을 반환한다.

BFS와 DFS의 차이점

• BFS (Breadth-First Search):
  • 너비 우선 탐색으로, 현재 노드의 모든 인접한 노드를 먼저 탐색한다.
  • 최단 경로를 찾는 데 유리하다.
  • 큐(Queue)를 사용하여 구현한다.
• DFS (Depth-First Search):
  • 깊이 우선 탐색으로, 현재 노드에서 갈 수 있는 한 깊이까지 탐색한 후, 더 이상 갈 수 없으면 되돌아와 다른 경로를 탐색한다.
  • 모든 경로를 탐색하는 데 유리하다.
  • 스택(Stack)이나 재귀 호출을 통해 구현한다.

예시

maps1 = [[1, 0, 1, 1, 1],
         [1, 0, 1, 0, 1],
         [1, 0, 1, 1, 1],
         [1, 1, 1, 0, 1],
         [0, 0, 0, 0, 1]]

maps2 = [[1, 0, 1, 1, 1],
         [1, 0, 1, 0, 1],
         [1, 0, 1, 1, 1],
         [1, 1, 1, 0, 0],
         [0, 0, 0, 0, 1]]

print(solution(maps1))  # 출력: 11
print(solution(maps2))  # 출력: -1

첫 번째 예시에서는 최단 경로의 길이가 11이므로 11을 반환하고, 두 번째 예시에서는 목적지에 도달할 수 없으므로 -1을 반환한다.

결론

이 포스트에서는 게임 맵에서 최단 경로를 찾는 문제를 BFS 알고리즘을 사용하여 해결하는 방법을 알아보았다.
BFS는 너비 우선 탐색으로 최단 경로를 찾기에 매우 적합하다. DFS와 BFS의 차이점을 이해하고, 문제의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요하다고 생각된다.