[PS, Algorithm] - 게임 맵 최단거리 (코딩테스트 연습, LEVEL 2)

📒문제

📌풀이

from collections import deque
INF = int(1e9)

def solution(maps):
    n = len(maps) # n = 행 개수, m = 열 개수
    m = len(maps[0])
    
    def bfs(row, col):
        q = deque()
        
        visit = [[INF for _ in range(m)] for _ in range(n)]
        d_row = [0, 0, -1, 1]
        d_col = [-1, 1, 0, 0]
        
        q.append((row, col, 1))
        visit[row][col] = 1
        
        while q:
            c_row, c_col, dist = q.popleft()
            dist += 1
            
            for i in range(4):
                nx_row = c_row + d_row[i]
                nx_col = c_col + d_col[i]
                
                if 0<=nx_row<n and 0<=nx_col<m:
                    if maps[nx_row][nx_col] != 0 and dist < visit[nx_row][nx_col]:
                        q.append((nx_row, nx_col, dist))
                        visit[nx_row][nx_col] = dist
                
                if nx_row == n-1 and nx_col == m-1: return visit[n-1][m-1]
                
        
        return -1
            
        
    return bfs(0, 0)

그냥 흔한 격자상에서의 최단거리 문제이므로 당연히 BFS를 써서 풀어야겠다고 생각했다.

1. 이런 문제를 풀 때는 queue에 정점을 넣을 때 시작점부터의 거리도 같이 묶어서 넣어주는 것이 좋다.
2. BFS는 알고리즘의 특성상 도착점에 도달했다면 그 때가 바로 시작점으로부터 도착점까지 최단거리로 도착한 경우가 된다. (더 멀리 둘러 가는 경우는 아직 queue에서 대기중이기 때문) 따라서, 다른 비교 없이, 도착점 좌표에 도달했다면 그 즉시 알고리즘을 종료한다.(더 효율적이게!)

이미 알고 있는 사실들이지만 한 번 리마인드 하기에 좋은 문제였다.