[Python/파이썬] LeetCode 1368번 Minimum Cost to Make at Least One Valid Path in a Grid

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/

코드

from collections import deque


def minCost(grid):
    n = len(grid)
    m = len(grid[0])

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    count = [[int(1e9)]*m for _ in range(n)]
    count[0][0] = 0
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        if x == n-1 and y == m-1:
            continue
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 여기서 방향 바꿈
                if i != grid[x][y]-1 and count[x][y]+1 < count[nx][ny]:
                    q.append((nx, ny))
                    count[nx][ny] = count[x][y]+1
                # 방향 안 바꿈
                elif i == grid[x][y]-1 and count[x][y] < count[nx][ny]:
                    q.append((nx, ny))
                    count[nx][ny] = count[x][y]

    return count[n-1][m-1]

 

BFS는 보통 최적의 해, 그러니까 이런 격자 내의 경로 문제에서는 최단 경로를 구할 때 많이 사용하는데, 이 문제는 그런 경우가 아니다. 이 문제에서는 경로의 길이가 아닌 방향 변경 횟수를 최소로 가지며 목적지에 도달하는 것을 구하고 있다.

 

그래서 위 코드에서는 목적지인 `(n-1, m-1)`에 도달했다 하더라도 바로 끝내지 말고, 남은 큐에 대해서도 다 처리하도록 했다. 왜냐하면 더 긴 거리를 걸려서 오더라도 방향 변경 횟수가 더 적은 경로가 있을 가능성이 있기 때문이다. 처음 발견한 경로가 방향 변경 횟수 측면에서 최적이라는 보장이 없으므로, 모든 가능한 경로를 탐색해야 한다.