🐹 게임 맵 최단거리

1. 문제 링크

게임 맵 최단거리

2. 코드

from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
INF = int(1e9)

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    distance = [[INF] * m for _ in range(n)]
    distance[0][0] = 1
    q = deque([])
    q.append((0, 0))
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                if distance[nx][ny] > distance[x][y] + 1:
                    distance[nx][ny] = distance[x][y] + 1
                    q.append((nx, ny))

    if distance[n-1][m-1] == INF:
        return -1
    
    return distance[n-1][m-1]

• 정확성 테스트

  테스트 1 〉	통과 (0.04ms, 10.2MB)
  테스트 2 〉	통과 (0.03ms, 10.4MB)
  테스트 3 〉	통과 (0.06ms, 10.2MB)
  테스트 4 〉	통과 (0.04ms, 10.2MB)
  테스트 5 〉	통과 (0.04ms, 10.2MB)
  테스트 6 〉	통과 (0.06ms, 10.4MB)
  테스트 7 〉	통과 (0.11ms, 10.4MB)
  테스트 8 〉	통과 (0.05ms, 10.2MB)
  테스트 9 〉	통과 (0.07ms, 10.2MB)
  테스트 10 〉	통과 (0.10ms, 10.2MB)
  테스트 11 〉	통과 (0.04ms, 10.3MB)
  테스트 12 〉	통과 (0.03ms, 10.2MB)
  테스트 13 〉	통과 (0.09ms, 10.2MB)
  테스트 14 〉	통과 (0.08ms, 10.2MB)
  테스트 15 〉	통과 (0.06ms, 10.2MB)
  테스트 16 〉	통과 (0.02ms, 10.2MB)
  테스트 17 〉	통과 (0.06ms, 10.4MB)
  테스트 18 〉	통과 (0.02ms, 10.2MB)
  테스트 19 〉	통과 (0.01ms, 10.4MB)
  테스트 20 〉	통과 (0.01ms, 10.3MB)
  테스트 21 〉	통과 (0.01ms, 10.2MB)

• 효율성 테스트

  테스트 1 〉	통과 (15.05ms, 10.3MB)
  테스트 2 〉	통과 (7.80ms, 10.3MB)
  테스트 3 〉	통과 (9.49ms, 10.5MB)
  테스트 4 〉	통과 (12.80ms, 10.4MB)

3. 해설

최단 거리를 구하기 위해 bfs 알고리즘을 사용한다.

각 위치의 최단거리를 나타내는 이차원 배열 distance를 무한대 값으로 초기화해주고 현재 위치(0, 0)만 1로 초기화해준다.

bfs를 돌며 map 안의 범위이면서 map이 1일 때 최단 거리를 갱신해준다. 최단 거리는 이전 위치 + 1의 값이다.

도착 위치의 최단거리 값 distance[n-1][m-1]이 구하고자 하는 최단 거리이다. 이때 해당 값이 초기값(무한대)이면 해당 위치에 도달하지 못한 것이므로 -1을 리턴한다.