[BOJ][Python]17070 풀이

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

17070번: 파이프 옮기기 1

import sys; ssr = sys.stdin.readline

def f(cur_r, cur_c, cur_dir):
    global ans
    if cur_r == n-1 and cur_c == n-1:
        ans += 1
        return
    else:
        if cur_dir == 0 or cur_dir == 1:
            if cur_c+1 < n and board[cur_r][cur_c+1] != 1:
                f(cur_r, cur_c+1, 0)
        if cur_dir == 1 or cur_dir == 2:
            if cur_r+1 < n and board[cur_r+1][cur_c] != 1:
                f(cur_r+1, cur_c, 2)
        if cur_r+1 < n and cur_c+1 < n and board[cur_r+1][cur_c+1] != 1 and board[cur_r][cur_c+1] != 1 and board[cur_r+1][cur_c] != 1:
            f(cur_r+1, cur_c+1, 1)
                        
n = int(ssr())
board = [list(map(int, ssr().split())) for _ in range(n)]
board[0][0], board[0][1] = 2, 2
ans = 0
f(0, 1, 0)
print(ans)

문제를 잘 읽어야 한다는 걸 다시 한 번 느꼈던 문제입니다. 지문이 너무 구현 문제스러워서 그런가 너무 조건을 어렵게 생각했어요. 문제에서 이미 케이스에 따른 갈 수 없는 칸을 정해줬기 때문에 하라는대로만 하면 됩니다.

 

DP로 풀면 훨씬 런타임이 좋아질텐데 저는 헛짓을 좀 하느라 시간을 많이 써서 DP 풀이는 또 차차 추가해보겠습니다.

 

DP 풀이를 추가했습니다.

import sys; ssr = sys.stdin.readline

n = int(ssr())
board = [list(map(int, ssr().split())) for _ in range(n)]
dp = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
dp[0][1][0] = 1
for i in range(n):
    for j in range(2, n):
        if board[i][j] == 1:
            continue
        dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][1]
        if board[i-1][j] == 0 and board[i][j-1] == 0:
            dp[i][j][1] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]
        dp[i][j][2] = dp[i-1][j][1] + dp[i-1][j][2]
print(sum(dp[n-1][n-1]))

3차원 테이블을 써보는 건 처음인데 의미가 명확해서 그런가 이전의 배낭 문제같은 대표적인 2차원 DP 보다는 오히려 쉬웠던 것 같습니다. 테이블이 가지는 의미는 현재 칸을 끝으로 하는 파이프의 경우를 의미합니다. 가령 dp[0][1][0] = 1은 (0, 1)의 위치를 끝으로 하는 가로 파이프의 갯수가 1개 라는 뜻이죠(저는 가로, 대각, 세로를 순서로 했습니다). 이 말이 이해가 되면 점화식 자체는 아주 간단해서 갑자기 DFS로 풀 때 보다 쉽다고 느껴지기도 하더라구요.