[Programmers] Level 3. 경주로 건설

🔗 Problem Link

프로그래머스

---

❔Thinking

• (0,0)에서 (n,n)으로 가는 경주로를 건설할 때, 최소비용의 도로 건설비용을 반환한다.
• 직선도로는 100원, 방향이 바뀌는 구간(코너)는 500원의 비용이 든다.

---

💻Solution

from collections import deque
def solution(board):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    def bfs(board, dir):
        n = len(board)
        dp = [[int(1e9)]*n for _ in range(n)]
        dp[0][0] = 0
        q = deque([(0,0,0,dir)])
        while q:
            x, y, cost, d = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                nd = i
                if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0:
                    if nd == d:
                        ncost = cost + 100
                    else:
                        ncost = cost + 600
                    if ncost < dp[nx][ny]:
                        dp[nx][ny] = ncost
                        q.append((nx,ny,ncost,i))
        return dp[-1][-1]
    
    return min(bfs(board, 1), bfs(board, 3))

---

🗝️keypoint

1. bfs로 시작 지점부터 최소 비용으로 이동하는 구간을 생각한다.
2. 지나가는 칸의 수가 많더라도, 직선이 많은 경로가 코너가 많은 경로보다 효율적일 수 있다.
3. 도로가 건설된 방향을 저장하고 있어야, 이어진 도로에 코너가 생기는지 확인할 수 있다.