[백준 17070번] | 파이프 옮기기 1 | DP, DFS (파이썬)

문제 소개

17070번: 파이프 옮기기 1

파이프 옮기기1

파이프 옮기기1

가로 파이프에 세로파이프를 바로 연결할 수 없고, 대각 파이프는 파이프끝지점 기준 위 한칸 왼쪽 한칸이 비어있어야 한다(벽이면 안된다)

파이프 옮기기1

dfs로 풀어보려 했으나 계속 시간초과가 발생..

import sys
N = int(sys.stdin.readline())
room = [[0]*N for _ in range(N)]
for i in range(N):
    room[i] = list(map(int,sys.stdin.readline().split()))
directions = [(0, 1), (1, 0), (1, 1)]   # (0,1)가로, (1,0) 세로, (1,1) 대각
cnt = 0 

def dfs(x,y,d): # (x,y,d(파이프 놓은 방향))
    if x >= N or y >= N or room[x][y] == 1:
        return
    global cnt
    if (x,y) == (N-1,N-1):
        cnt += 1
        return
    for i in range(3): # i -> 0 가로, 1 세로, 2 대각 direction[0],[1],[2]
        if (d == 0 and i == 1) or (d == 1 and i == 0): # 가로 -> 세로, 세로 -> 가로 불가능함
            continue 
        nx,ny = x + directions[i][0],y + directions[i][1]
        if nx >= N or ny >= N or room[nx][ny]==1: # room 범위 벗어나는지, 벽인지 검사
            continue
        if i == 2 and (room[x][y+1] == 1 or room[x+1][y]): # 대각 파이프 놓을때 조건 검사
            continue
        dfs(nx,ny,i)
dfs(0,1,0) # (0,1,가로)

sys.stdout.write(f"{cnt}\n")

시간초과

pypy3로도 제출해봤는데 여전히 시간초과가 발생했다.

dfs로도 풀수 있을거 같은데 알고리즘 분류를 보니 dp로 분류되어 있었다.

dp로 풀어보기로 결정

문제 풀이

import sys
N = int(sys.stdin.readline())
room = [[0] * N for _ in range(N)]
for i in range(N):
    room[i] = list(map(int,sys.stdin.readline().split()))
dp = [[[0] * 3 for _ in range(N)] for _ in range(N)] # [x][y]에서   
dp[0][1][0] = 1 # 초기값(0,1) 가로 시작
for i in range(N):
    for j in range(2,N):
        if room[i][j] == 1: # 벽이면
            continue
        dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2] # 가로방향 가능한 경우의수 = 이전에서 가로 + 대각 경우의수

        if i >= 1:
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2] # 세로 = 이전에서 세로 + 대각

        if i > 0 and room[i-1][j] == 0 and room[i][j-1] == 0:
            dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1]+ dp[i-1][j-1][2]
sys.stdout.write(f"{sum(dp[N-1][N-1])}\n")

 

dp[i][j][k] = (i, j) 위치에 방향k로 파이프를 놓을 수 있는 경우의 수

이때 k == 0: 가로, k == 1 세로, k == 2 대각이다

 

for j in range(2, N) 0,1에서 시작하기때문에 2부터 시작한다

 

dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]

dp[i][j][0]

(i, j)에서 가로로 놓을수 있는건 (i, j-1)에서 가로로 놓았을때와 대각으로 놓았을때 밖에 없다(세로 -> 가로는 불가능)

 

dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]

(i, j)에 세로 파이프로 도달하려면 바로위(i-1,j)에서 세로 방향이었거나, (i-1,j)에서 대각 이었야 한다

 

if room[i-1][j] == 0 and room[i][j-1] == 0

(i, j)에 대각으로 도달하려면 일단 위쪽(i-1, j)과 왼쪽 (i, j-1) 이 벽이 아니여야한다

dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]

대각선 위(i-1, j-1)에서 가로, 세로, 대각 일때 가능하다

 

점화식을 어떻게 해야할지 모르겠어서 풀이를 참고했다(방향을 dp 테이블에서 어떻게 구현해야 할지가 떠오르지 않았다)

 

정답