문제 링크

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

문제 설명

• 파이프를 밀어서 끝으로 옮긴다
• 파이프의 방향에 따라 옮길 수 있는 위치, 모양이 정해져 있다
• 경우의 수 출력

풀이

• 어떤 한 좌표로 갈 수 있는 경우는 총 3가지이다
• 그런데 각 모양마다 이전에 어떤 모양이었는지에 따라, 올 수 있는지가 다르다
• 그래서 각 좌표마다 3차원 배열로 이전에 어떤 모양이었는지 적는다
• 그리고 특정 좌표로 올 때 빈 칸이어야 하는 구역들이 있는데, 이것도 모양에 따라 다르기 때문에 모양마다 조건을 넣어준다

느낀 점

• 처음에 유형을 봐버려서 다른 풀이가 잘 떠오르지 않았다
• 왜 DP를 사용해야 하는지 더 생각해볼 필요가 있을 것 같다
• DFS는 안될까?

코드

def init():
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    dp = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
    dp[0][1][0] = 1
    return n, board, dp


n, board, dp = init()
for y in range(n):
    for x in range(2, n):
        if sum(board[y][x-1:x+1]) == 0:
            dp[y][x][0] = dp[y][x-1][0] + dp[y][x-1][2]
        if board[y-1][x] == 0 and board[y][x] == 0:
            dp[y][x][1] = dp[y-1][x][1] + dp[y-1][x][2]
        if sum(board[y-1][x-1:x+1]) + sum(board[y][x-1:x+1]) == 0:
            dp[y][x][2] = sum(dp[y-1][x-1])
print(sum(dp[-1][-1]))