[파이썬] 백준 10251 : 운전 면허 시험 (플레5)

[파이썬] 백준 10251 : 운전 면허 시험 (플레5)

• https://www.acmicpc.net/problem/10251
  

---

풀이

방향성 생각

• 상태 공간 나누기
  • x좌표, y좌표, x,y에 들어오는 진입 방향, 누적 회전 수
  • 상태공간 나누는 기준이 G가 아닌건, G 범위가 너무 크다.
  • G 공간을 리스트로 나누거나 딕셔너리로 나눠도 메모제이션이 되지 않을 가능성이 매우 높아서 BFS랑 다를바가 없다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T):

    H,W,L,G = map(int, input().split())

    # 가로이동 : hor[i][j] (j,i)에서 (j+1,i)로 이동
    hor = [list(map(int, input().split())) for _ in range(H)]

    # 세로이동 : ver[i][j] (j,i+1)에서 (j,i)로 이동
    ver = [list(map(int, input().split())) for _ in range(H-1)]

    # dp[y][x][x,y로 오는 방향 0:가로 1:세로][x,y까지 누적 회전 수] = 남은 연료 수
    dp = [[[[-1]*(201) for _ in range(2)] for _ in range(W)] for _ in range(H)]
    dp[0][0][0][0] = G  
    dp[0][0][1][0] = G 

    # 행 초기화
    for j in range(1,W):
        g = dp[0][j-1][0][0] - hor[0][j-1]
        if g < 0: break
        dp[0][j][0][0] = g

    # 열 초기화
    for i in range(1,H):
        g = dp[i-1][0][1][0] - ver[i-1][0]
        if g < 0: break
        dp[i][0][1][0] = g

    # dp 업데이트
    for i in range(1,H):
        for j in range(1,W):
            for t in range(200):

                hv = dp[i-1][j][0][t] - ver[i-1][j] # 이전 노드에는 h 방향, 현재 노드에는 v 방향으로 접근 (회전 수 + 1)
                if hv>=0:
                    dp[i][j][1][t+1] = max(dp[i][j][1][t+1],hv)

                vv = dp[i-1][j][1][t] - ver[i-1][j] # 이전 노드, 현재 노드 모두 v 방향 (회전 수 그대로)
                if vv>=0:
                    dp[i][j][1][t] = max(dp[i][j][1][t],vv)

                hh = dp[i][j-1][0][t] - hor[i][j-1] # 이전 노드, 현재 노드 모두 h 방향 (회전 수 그대로)
                if hh>=0:
                    dp[i][j][0][t] = max(dp[i][j][0][t],hh)

                vh = dp[i][j-1][1][t] - hor[i][j-1] # 이전 노드에는 v 방향, 현재 노드에는 h 방향으로 접근 (회전 수 + 1)
                if vh>=0:
                    dp[i][j][0][t+1] = max(dp[i][j][0][t+1],vh)

    # 최솟값 찾기 : 도착점에서 배열 순회 남은 g가 0보다 크면 도착 가능
    min_turn = float('inf')
    for d in range(2):
        for t in range(201):
            if dp[-1][-1][d][t] >= 0:
                min_turn = min(min_turn,t)

    # 정답 : 이동 수 * L + 회전 수
    if min_turn == float('inf'):
        print(-1)
    else:
        answer = min_turn + ((H-1)+(W-1))*L
        print(answer)

코멘트

• 문제 자체는 다차원 DP 잘 풀면 어렵진 않은데, 파이썬으로 풀이하려면 시간제한이 좀 빡빡해서 무조건 다차원 리스트로 풀어야하는듯

• 첫 풀이는 상태공간 낭비하는걸 막으려고, 이중 딕셔너리로 풀이

  • 각 좌표 (x,y)마다 들어오는 경우의 수가 4개로 정해져있어서, for에서 반복을 최대한 줄이는 식으로 풀이

  • 메모리 초과엔딩