[Python] 2666 - 벽장문의 이동 (골드5)

1. 문제 설명

https://www.acmicpc.net/problem/2666

2666번: 벽장문의 이동

 

---

2. 아이디어

여전히 기억에 남는 재밌는 문제였다.

속 편하게 3차원으로 풀어버렸다. 이유를 대강 서술하자면 다음과 같다.

 

첫 번째, cache를 1차원으로 잡고 1을 끌어오는 거리만큼 카운트를  한다.

좌하단 그림처럼 좌측에서 1을 끌어오느냐,

우측에서 1을 끌어오느냐에 따라 경우의 수를 따로 판단할 방법없음

 

두 번째, cache를 2차원으로 잡고 [open1][open2] 인자를 받으면서 cache값을 누적한다.

for문 안에 재귀를 넣거나 여러 방법을 시도하다가 조건을 걸기가 너무 까다로워서 포기.

 

결론, cache를 아예 3차원으로 만들고 [열고 싶은 곳][열린 문1][열린 문2]로 잡았다.

현재 인덱스에서 이동하고 싶은 인덱스까지의 거리까지 계산이 가능해짐.

문제는 min(이동하려는 인덱스, 현재 인덱스)가 하단 그림에 파란색으로 별표 친 부분처럼

탐색이 꼬이는 경우가 발생했다.

그래서 아예 열린문1을 끌어오는 경우와 열린문2를 끌어오는 경우를 따로 계산해서

서로의 최솟값을 누적시켰다.

 

차원을 단축 시키기 위해서 인덱스를 첫 번째 인덱스 + 두 번째 인덱스 + 전체 문의 개수로 잡거나

비트마스킹으로 이동하는 방법도 있지만..지금도 그런식으로 인덱스 접근은 너무 머리 아파서

웬만하면 쓰고 싶지 않다. ㅠ

 

---

3. 코드

import sys
input = sys.stdin.readline

n = int(input())
open1, open2 = map(int, input().split())
check_cnt = int(input())
check_num = [int(input()) for _ in range(check_cnt)]
cache = [[[-1]*(n+1) for _ in range(n+1)] for _ in range(check_cnt)]

def dfs(idx, open1, open2):
    if idx == check_cnt: # 깊이 제한
        return 0
    
    if not cache[idx][open1][open2] == -1:
        return cache[idx][open1][open2]
    
    move_open1 = dfs(idx+1, check_num[idx], open2) + abs(check_num[idx] - open1)
    move_open2 = dfs(idx+1, open1, check_num[idx]) + abs(check_num[idx] - open2)
    cache[idx][open1][open2] = min(move_open1, move_open2)
    
    return cache[idx][open1][open2]

def solution():
    print(dfs(0, open1, open2))

solution()