[Algorithm🧬] 백준 2666 : 벽장문의 이동

문제

DFS 섹션에 있었지만 어차피 DP 도 공부해야해서 이 분의 DP 풀이를 참고해서 풀었다.
https://stillchobo.tistory.com/109

점화식

dp[door1][door2][index] = min(abs(door1 - target) + solved(target, door2, index + 1),
                                  abs(door2 - target) + solved(door1, target, index + 1))

블로그 찾아보면 다들 저 점화식을 너무 당연하게 사용하는데.. 뭔소리야? 백번하고 이해했는데...

dp[door1][door2][index] #현재 상황에서 가장 적게 움직이는 방법은
# door1 을 움직일지 door2 를 움직일지 정해야 함.
# 그런데 지금 당장 가까운걸 선택한다고 되는게 아니고 모든 과정을 진행했을 때 작을 문을 선택해야함.
= min(

abs(door1 - target) # 열린 door1 을 움직이고
+ solved(target, door2, index + 1), # 지금까지 진행한거랑 현재 door1 을 움직여서 수행한 단계를 제외하고 남은 단계를 모두 수행한 것 중 가장 작은 값.
                                  
abs(door2 - target) # 열린 door2 를 움직이고 
+ solved(door1, target, index + 1)) # 지금까지 진행한거랑 현재 door2 을 움직여서 수행한 단계를 제외하고 남은 단계를 모두 수행한 것 중 가장 작은 값.


# 사실상 마지막 단계부터 보는 것이 맞는.. 문제.. 그렇게 생각하면 DFS 로도 풀 수 있을지도

DP

import sys

def solved(door1, door2, index):
    if index == t:
        return 0

    target = useOrder[index]
    dp[door1][door2][index] = min(abs(door1 - target) + solved(target, door2, index + 1),
                                  abs(door2 - target) + solved(door1, target, index + 1))

    return dp[door1][door2][index]



n = int(sys.stdin.readline())
open1, open2 = map(int, sys.stdin.readline().split())
t = int(sys.stdin.readline())
useOrder = [int(sys.stdin.readline()) for _ in range(t)]

dp = [[[0] * 21] * 21] * 21
dp = [[[0] * (order_n) for _ in range(n + 1)] for _ in range(n + 1)]

print(solved(open1, open2, 0))

DFS

import sys

def DFS(level, left, right, sum_move):
    global cnt
    
    # 그 중 가장 작은걸 골라야하므로 가지를 다 돌기 전에 지금까지 최솟값보다 더 커져버리면 out
    if cnt <= sum_move:
        return
    
    # 들어온 입력대로 문을 움직이면 완료
    if level >= t:
        cnt = sum_move
        return

    # 왼쪽이 움직일 수 있는 상황
    # 오른쪽 열린문보다 더 오른쪽이면 왼쪽이 움직이는건 낭비
    if useOrder[level] < right:
        DFS(level + 1, useOrder[level], right, sum_move + abs(left - useOrder[level]))
    # 오른쪽이 움직일 수 있는 상황
    # 왼쪽 열린문보다 더 왼쪽이면 오른쪽이 움직이는건 낭비
    if left < useOrder[level]:
        DFS(level + 1, left, useOrder[level], sum_move + abs(right - useOrder[level]))


n = int(sys.stdin.readline())
open1, open2 = map(int, sys.stdin.readline().split())
t = int(sys.stdin.readline())
useOrder = [int(sys.stdin.readline()) for _ in range(t)]

cnt = -1

DFS(0, min(open1, open2), max(open1, open2), 0)