[프로그래머스] 경주로 건설

hjoon·2022년 1월 13일
0

Problem Solving

목록 보기
9/13
post-thumbnail

[카카오 인턴] 경주로 건설


코드

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
dd = [0, 1, 2, 3]
INF = float('inf')


def solution(board):
    answer = float('inf')
    n = len(board)
    dp = [[[INF for _ in range(n)] for _ in range(n)] for _ in range(4)]  # 4방향에 대한 dp
    q = deque([[0, 0, 0, -1]])
    while q:
        x, y, cost, old_direct = q.popleft()

        if [x, y] == [n - 1, n - 1]:
            answer = min(answer, cost)
            continue

        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx < n and 0 <= yy < n:
                new_direct = dd[i]
                new_cost = cost + 100 if old_direct == -1 or old_direct == new_direct else cost + 600
                if board[xx][yy] == 0 and dp[new_direct][xx][yy] > new_cost:
                    dp[new_direct][xx][yy] = new_cost
                    q.append([xx, yy, new_cost, new_direct])
    return answer

접근 방식

BFS , dp

왜 dp를 사용해야 할까?

일단 (x,y) 좌표까지 도달하기 위해 필요한 비용을 dp에 저장하므로써 불필요한 경우를 걸러내어 시간복잡도를 줄일 수 있다.

C 경로를 거쳐 (x, y)에 도달했던 적이 있을 때,
A, B 경로를 거쳐 (x, y)에 도달한 상황을 생각해보자.

dp[x][y] = 10 # C 경로로 x,y 에 도달할 때 소요된 비용

case 1: A 경로를 거쳐 x, y에 도달할 때 소요된 비용 == 7
case 2: B 경로를 거쳐 x, y에 도달할 때 소요된 비용 == 12

case 1의 경우 dp[x][y] 를 7로 갱신하고 stack에 담아야 한다.

  • C 경로보다 적은 비용을 가지는 A 경로에 대해 고려해야한다. (최소 비용을 구하는게 문제의 목적이니까)

case 2의 경우 stack에 담지않는다.

  • B 경로보다 비용이 적은 C 경로가 존재하므로 B 경로에 대해 더이상 고려할 필요 없다. (B경로보다 비용이 적게 드는 경로가 존재하니까)

왜 3차원 dp일까?

(x, y)에 접근할 수 있는 방향의 수는 위, 아래, 오른쪽, 왼쪽 총 4개이고
접근하는 각 방향에 따라서 소요되는 비용이 서로 다르다.

  • 위에서 (x,y)로 내려오는 경우 (2가지)
    1. ↓ ↓ : 직선 도로를 타고 쭉 내려오는 경우 (old cost + 100)
    2. 코너를 꺾어서 내려오는 경우 (2가지)
      2-1. → ↓ : 오른쪽으로 진행하다 아래로 꺾는 경우 (old cost + 100 + 500)
      2-2. ↓ ← : 왼쪽으로 진행하다가 아래로 꺾는 경우 (old cost + 100 + 500)

위와 같은 이유로 (x, y)까지 도달하기 까지 소요되는 비용을 방향마다 다르게 고려해야한다.
👉 dp[방향][x][y]

0개의 댓글