BFS로 풀다가 시간초과 나서 DP로 해결한 문제.
1. 요약
2칸을 차지하는 파이프라인을 바라보는 방향에 대해 직진 또는 회전 후 직진하여, 파이프의 한 쪽 끝을 (N, N)으로 보낼 때 나올 수 있는 경우의 수를 구하는 문제. 이 때, (y, x)칸이 0일 때만 이동 가능하다.
2. 아이디어
파이프의 한 쪽 끝만 고려하자. 그리고 바로 DP를 문제에 적용하기엔 막연하니 DFS를 이용한 완전 탐색으로 먼저 구현한다.(저의 경우 DFS로 구현하여 제출하면 69%에서 시간초과 났습니다. 주석으로 처리한 부분인 완전탐색으로 구현한 부분입니다.)
파이프의 한쪽 끝이 다음 칸으로 이동을 할 수 있는 지 알아보기 위해, 문제에서 주어진 이동 조건을 고려한다. 이후 파이프의 한 쪽 끝이 (N, N)에 도달하면 경우의 수를 하나 증가시킨다.
여기까지 구현했으면, 이제 DP를 고려한다. (y, x)칸에서 (N, N)으로 갈 수 있는 경우의 수를 메모이제이션 한다. 이 때, 방향도 고려해야하므로 3차원 배열을 만들어서 경우의 수를 기록한다.
(e.g. (y, x)에서 가로방향을 향하고 있는 파이프가 (N, N)에 도달 할 수 있는 경우의 수)
만약 방향으로 고려하지 않은 상태에서 메모이제이션을 한다면, to 방향을 바라보고 있는 (y ,x)칸에 있는 파이프라인은 자신이 바라보는 방향 때문에 (N, N)칸에 도달 할 수 없음에도 불구하고, 메모이제이션된 값이 있기 때문에 도달한다고 생각한다.
예를 들어 예제2번에서 파이프의 한 쪽 끝이 2행 3열에 있고 대각선 방향을 바라본다고 하자. 파이프 한 쪽 끝이 2행 4열로 이동할 때, 파이프의 한 쪽 끝은 가로 방향을 바라보게 되고 2행 4열에 메모이제이션 된 값이 있으니 이부분을 반영한다. 하지만 2행 4열에서 가로 방향을 바라보는 파이프의 한 쪽 끝은 (N, N)에 도달할 수 없다. 방향을 고려해야하는 이유이다.
마지막으로 (N, N)칸에 있는 값이 0인지 1인지도 확인하자. 만약 (N, N)에 있는 칸이 1이면 메모이제이션된 값이 없으므로 사살상 완전탐색이 되어 시간초과가 난다.
3. 코드
import sys
WIDTH = 0
HEIGHT = 1
DIAG = 2
n = int(sys.stdin.readline().rstrip())
arr = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
table = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(3)]
d = [[0,1], [1,0], [1,1]]
def isin(y,x):
if -1<y<n and -1<x<n: return True
return False
def check(to, y, x):
if to == DIAG:
if arr[y][x] == 0 and arr[y-1][x] == 0 and arr[y][x-1] == 0: return True
elif arr[y][x] == 0: return True
return False
def solve(to, y, x):
global table
#answer = 0
if [y, x] == [n-1, n-1]: return 1
if table[to][y][x]: return table[to][y][x]
for i in range(3):
ny = y + d[i][0]
nx = x + d[i][1]
ok = False
if isin(ny, nx):
if to == WIDTH and i != HEIGHT: ok = check(i, ny, nx)
elif to == HEIGHT and i != WIDTH: ok = check(i, ny, nx)
elif to == DIAG: ok = check(i, ny, nx)
if ok:
table[to][y][x] += solve(i, ny, nx)
#answer += solve(i,ny,nx)
#return answer
return table[to][y][x]
if arr[-1][-1] == 1: print(0)
else: print(solve(WIDTH, 0, 1))