🟩 [백준] [Python] [Gold5] 17070번_파이프 옮기기 1

문제

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

17070번: 파이프 옮기기 1

풀이

import sys
count = 0
N = int(input())
home = []

for _ in range(N):
    home.append([int(x) for x in sys.stdin.readline().rstrip().split()])

def dfs(x,y,state): # state 0: 가로, 1: 세로 , 2: 대각선
    global count
    if x == N - 1 and y == N - 1:
        count += 1
        return

    if state == 0:
        if y == N - 1: # 이동불가
            return

        if 0 <= x < N and 0 <= y + 1 < N and home[x][y + 1] == 0:
            dfs(x, y + 1, 0)

        if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][
            y + 1] == 0:
            dfs(x + 1, y + 1, 2)

    elif state == 1:
        if x == N - 1: # 이동불가
            return

        if 0 <= x + 1 < N and 0 <= y < N and home[x + 1][y] == 0:
            dfs(x + 1, y, 1)

        if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][
            y + 1] == 0:
            dfs(x + 1, y + 1, 2)

    elif state == 2:
        if 0 <= x < N and 0 <= y + 1 < N and home[x][y + 1] == 0:
            dfs(x, y + 1, 0)

        if 0 <= x + 1 < N and 0 <= y < N and home[x + 1][y] == 0:
            dfs(x + 1, y, 1)

        if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][
            y + 1] == 0:
            dfs(x + 1, y + 1, 2)

dfs(0,1,0)
print(count)

맨 처음 DFS를 통해 풀었다. 근데 시간초과가 발생해서 pypy3 로 풀었는데 통과하였다. 

그래서 찾아본 결과 DP 를 통해 풀 수 있는 문제였다. 

 

# 백준 17070번 문제 - 파이프 옮기기 1
def solution():
    dp[0][0][1] = 1
    for i in range(2, n):
        if graph[0][i] == 0:
            dp[0][0][i] = dp[0][0][i - 1]
    for r in range(1, n):
        for c in range(1, n):
            if graph[r][c] == 0 and graph[r][c - 1] == 0 and graph[r - 1][c] == 0:
                dp[1][r][c] = dp[0][r - 1][c - 1] + dp[1][r - 1][c - 1] + dp[2][r - 1][c - 1]
            if graph[r][c] == 0:
                dp[0][r][c] = dp[0][r][c - 1] + dp[1][r][c - 1]
                dp[2][r][c] = dp[2][r - 1][c] + dp[1][r - 1][c]
    print(sum(dp[i][n - 1][n - 1] for i in range(3)))
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(3)]
solution()