[プログラマー]コース建設(Python Python Python Python Python Python Python)


👉 科斯建设



マイコード

from collections import deque


def solution(board):
    size = len(board[0])
    visit = [[-1] * size for _ in range(size)]
    d = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # y,x 위, 오른쪽, 아래, 왼쪽
    result = []

    def bfs():
        q = deque([[0, 0, 0, (0, 0)]])
        while q:
            y, x, cost, od = q.popleft()
            for i in range(4):
                ny = y + d[i][0]
                nx = x + d[i][1]
                money = 100 if od == d[i] or cost == 0 else 600  # 전과 같은 방향이거나 시작 +100 / 코너 +600
                ncost = cost + money
                if (
                    (0 <= ny < size and 0 <= nx < size)  # 경계
                    and board[ny][nx] == 0  # 벽 아님
                    and (visit[ny][nx] == -1 or visit[ny][nx] >= ncost)  # 처음오거나 더 좋은 비용의 길
                ):
                    visit[ny][nx] = ncost
                    q.append([ny, nx, ncost, d[i]])

    bfs()
    return visit[-1][-1]

チップ

  • などの費用がかかっても、方向によってはさらに安くなる場合がありますので、確認が必要です.
    (visit[ny][nx]>=ncostこの部分は最初は>で終わりました...)
  • bfsと共にdpの問題を考える
  • 👉 おしゃべり


    これは思いがけない経典の問題です!
    bfsとdpの2つの概念を使う問題