[BOJ] Q2666 벽장문의 이동

[BOJ] Q2666 벽장문의 이동

Question

Language: Python

Difficulty: Gold 5

특정 벽장 문을 열기 위해서는 닫혀 있는 문을 이동시켜야한다. 그러면, 열려 있는 두 문중에 하나를 선택해서 해당 문쪽으로 이동 시키는 작업을 진행해야한다.

그래서, 특정 문을 열기 위해, 열린 2개의 문에 대해 아래와 같은 점화식을 세워 볼 수 있다.

dp[next_door][door1][door2]=min(
        abs(next_door-door1) + dfs(count+1,next_door,door2),
        abs(next_door-door2) + dfs(count+1,door1,next_door)
    )

특정 문을 열기 위해, 열려 있는 문들 중에서, 거리값을 비교해서 초기화해준다.

해당 문제의 유형은 dfs 와 dp를 응용한 dfs+dp 응용 문제이다.

Solution 1

from math import inf
def dfs(count,door1,door2):
    global dp
    if count == n_movements:
        return 0

    next_door=movements[count]

    dp[next_door][door1][door2]=min(
        abs(next_door-door1) + dfs(count+1,next_door,door2),
        abs(next_door-door2) + dfs(count+1,door1,next_door)
    )

    return dp[next_door][door1][door2]  
if __name__ == "__main__":
    n_doors=int(input())
    door1,door2=map(int,input().split())
    n_movements=int(input())
    movements=[]
    for _ in range(n_movements):
        movements.append(int(input()))

    dp=[[[0] *(n_doors+1) for _ in range(n_doors+1)]for _ in range(n_doors+1)]
    print(dfs(0,door1,door2))

사실 해당 문제는 n의 크기가 매우 작으므로, 단순 dfs을 통하 bruteforce 방식을 취해도 풀이가 가능하다.

Solution 2

from math import inf
def dfs(cnt,door1,door2,move_count):
    global min_result
    if cnt==n_movements:
        min_result=min(min_result,move_count)
        return
    next_door=movements[cnt]
    dfs(cnt+1, next_door,door2,move_count+abs(next_door-door1))
    dfs(cnt+1, door1,next_door,move_count+abs(next_door-door2))
    
if __name__ == "__main__":
    n_doors=int(input())
    door1,door2=map(int,input().split())
    n_movements=int(input())
    movements=[]
    for _ in range(n_movements):
        movements.append(int(input()))

    min_result=inf
    dfs(0,door1,door2,0)
    print(min_result)