[프로그래머스] 게임 맵 최단거리 (python) / DFS, BFS

💻 프로그래머스 - 게임 맵 최단거리

👉 문제 보러 가기

 

🧩 문제 설명

게임 맵 최단거리 문제

 

게임 맵 최단거리 문제

 

게임 맵 최단거리 문제

🧩문제 요약

2차원 게임 맵에서 (0, 0) 위치에서 출발하여 (n-1, m-1) 목표 지점으로 이동해야 합니다.
이동은 상하좌우 네 방향으로만 가능하며,

• 1: 이동할 수 있는 칸
• 0: 벽이어서 이동할 수 없는 칸입니다.

이때, 캐릭터가 최단 거리로 목표 지점까지 도달할 수 있는 거리를 반환해야 하며,
도달할 수 없는 경우에는 -1을 반환합니다.

• 출발 지점: (0, 0)
• 도착 지점: (n-1, m-1)
• 맵 크기: n x m
• 이동 방향: 상, 하, 좌, 우
• 갈 수 있는 칸: 1
• 벽: 0
• 최단 거리 반환 (못 가면 -1)

 

---

🔍 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)]) # 0,0은 시작위치, 1은 첫칸부터 시작하므로 거리 1로 설정
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True # 0,0은 방문했으니 True로 설정
    
    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 not visited[nx][ny] and maps[nx][ny] == 1:
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))
                
    return -1

 

✅ 풀이해석

이 문제는 최단 거리를 구하는 문제이므로, BFS(너비 우선 탐색)을 사용하는 것이 적절합니다.
BFS는 가까운 노드부터 탐색하기 때문에, 가장 먼저 도착한 경로가 항상 최단 거리입니다.

 

1. 기본 세팅

    n = len(maps) # 행 개수
    m = len(maps[0]) # 열 개수

• maps는 2차원 리스트이며, n x m 크기의 맵입니다.

   directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 위, 아래, 왼쪽, 오른쪽

• 상, 하, 좌, 우로 움직일 수 있도록 방향벡터를 설정합니다.

    queue = deque([(0, 0, 1)]) # 0,0은 시작위치, 1은 첫칸부터 시작하므로 거리 1로 설정
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True # 0,0은 방문했으니 True로 설정

• queue에는 (x좌표, y좌표, 현재까지의 거리)를 저장합니다.
• visited 배열은 각 위치를 한 번만 방문하기 위해 사용합니다.
• (0,0)에서 출발하므로 시작 위치를 큐에 넣고 방문 처리(True)합니다.

 

2. BFS 탐색 시작

    while queue: # 큐에 남은 좌표가 있을 때까지 반복.
        x, y, dist = queue.popleft()

• 큐에서 현재 위치를 꺼냅니다.
• dist는 현재 위치까지 이동한 칸 수입니다.

        if x == n - 1 and y == m - 1:
            return dist

• 목표 지점에 도착하면 그때의 dist를 반환합니다.
  즉, 도착했을 때의 거리 = 최단 거리입니다.

 

3. 상하좌우로 이동

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

• 현재 위치에서 상하좌우로 이동한 좌표를 계산합니다.

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and maps[nx][ny] == 1:
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))

• 맵을 벗어나지 않으면서, 방문하지 않았고, 이동 가능한 칸 일 경우에만:
  • 방문 처리 후 이동한 위치와 거리를 큐에 추가합니다.

 

4. 도달할 수 없는 경우

    return -1

• BFS 탐색을 마쳤는데도 목표 지점에 도달하지 못했다면, 막혀있는 경우이므로 -1을 반환합니다.

 

---

✨ 마무리 정리

• 이 문제는 최단 경로를 구하는 전형적인 문제로, DFS보다 BFS가 적합합니다.
  • BFS는 가까운 곳부터 차례대로 탐색하므로,
  • 가장 먼저 도착한 경로가 항상 최단 거리입니다.
  • 한 번 방문한 곳은 다시 탐색하지 않기 때문에 불필요한 연산이 줄어들고 효율적입니다.

 

 

 

 

---

📌 아직 배우는 중이라 부족한 부분이 있을 수 있습니다.
혹시 잘못된 내용이나 더 나은 방법이 있다면 알려주세요 🙏
감사합니다! 😄