[Python] 5069번 미로에 갇힌 상근

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

5069번: 미로에 갇힌 상근

---

 

24/02/01

 

 

DP문제로, 골드 4보다는 훨씬 어렵다고 느껴졌던 문제입니다.

---

 

문제 접근 방식:

 

 

처음에 접근했던 방식은, 초기 몇 개의 항을 문제에서 주어진 그대로 브루트포스+백트래킹을 사용하여 구한 뒤, OEIS를 이용해 답을 구한 방식이었습니다.

 

이 문제에 대한 OEIS링크는 아래에 있습니다.

 

https://oeis.org/A002898 

A002898 - OEIS

 

이후, 이 문제에 대한 태그를 확인했고, DP문제라는 것을 알게 된 후에 어떻게 하면 DP로 접근할 수 있을지를 생각해보았습니다.

 

2024.01.05 - [알고리즘/백준 문제 풀이] - [Python] 17370번 육각형 우리 속의 개미

[Python] 17370번 육각형 우리 속의 개미

 

그러던 중, 다음과 같은 문제를 풀었던 것이 생각났습니다.

 

이 문제의 핵심 아이디어는 육각형의 격자를 어떻게 하면 2차원 상의 좌표로 잘 옮길 수 있을지에 대한 문제였습니다.

 

이를 참고하여, 다음과 같은 DP식을 세웠습니다.

 

$$DP[N][i][j] = N\text{번 이동했을 때 }i,j\text{에 도착하는 경우의 수}$$

 

처음에 상근이가 있는 방의 좌표는 $(0, 0)$이지만, 구현 상의 편의성을 위해 $(50, 50)$으로 설정했습니다.

 

이후 DP식의 전이는 이전 좌표에서 다음 좌표로 움직일 수 있어야 하므로 다음과 같은 점화식으로 나오게 됩니다.

 

$$DP[N][i][j] = DP[N-1][p][q] (p, q\text{ 는 }i, j \text{로 갈 수 있는 좌표들})$$

 

이 점화식을 그대로 구현하면 됩니다.

 

우리가 구하고자 하는 값은 $N$번 움직였을 때, 처음 상근이가 있는 방의 좌표로 돌아오는 경우의 수를 세는 것이므로, $DP[N][50][50]$의 값을 출력하면 됩니다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 5069번 미로에 갇힌 상근
# DP
'''
접근 방법:
DP[N][i][j] = N번 이동했을 때 i,j에 도착하는 경우의 수
중심점이 0, 0이지만 이걸 50, 50으로 간주해보자.
그리고 100짜리 배열을 선언한다.
'''
dr, dc = [1, 2, 1, -1, -2, -1], [1, 0, -1, -1, 0, 1]
DP = [[[0 for _ in range(100)] for _ in range(100)] for _ in range(15)]
DP[0][50][50] = 1
for n in range(1, 15):
    for i in range(100):
        for j in range(100):
            for k in range(6):
                br, bc = i+dr[k], j+dc[k]
                if 0 <= br < 100 and 0 <= bc < 100:
                    DP[n][i][j] += DP[n-1][br][bc]
for _ in range(int(input())):
    print(DP[int(input())][50][50])