[프로그래머스] Lv.3 경주로 건설 [Python, 파이썬] KAKAO

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/67259
• 🔑 BFS
  • 아래쪽으로 먼저 갈 때
  • 오른쪽으로 먼저 갈 때
  • 두 가지 경우를 탐색

from collections import deque

def solution(board):
    
    n = len(board)
    mx = [-1, 1, 0, 0]
    my = [0, 0, -1, 1]

    def bfs(x, y, cost, d):
        visit = [[0] * n for _ in range(n)]

        Q = deque([(x, y, cost, d)])

        while Q:
            x, y, cost, d = Q.popleft()

            for i in range(4):
                nx, ny = x + mx[i], y + my[i]

                if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:
                    if d == i:
                        newcost = cost + 100
                    else:
                        newcost = cost + 600
                    
                    if visit[nx][ny] == 0 or visit[nx][ny] > newcost:
                        visit[nx][ny] = newcost
                        Q.append((nx, ny, newcost, i))

        return visit[n-1][n-1]

    return min(bfs(0, 0, 0, 1), bfs(0, 0, 0, 3))