백준 17070 파이프 옮기기1

궁금한 점

• 파이썬에서 재귀를 하는데 시간이 오래 안걸리는 방법이 있는지? 꼭 찾아보자. c++는 depth 백만까지도 dfs로 풀이 가능하다는데 파이썬도 그런지 확인 필요.

코드1

• dfs 풀이
• 효율성 테스트에서 시간 초과
• 코드 내용
  • dfs함수는 row, col, state 3개 인자를 받는다.
  • state에 따라서 갈 수 있는 주변 노드를 확인하여 해당 노드를 다시 dfs 함수에 넣는다.
  • 함수가 재귀적으로 생성되며, (N,N)에 도달할 경우 ans + 1  

import sys

n= int(sys.stdin.readline())
graph= [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
n-=1
ans = 0
def dfs(r,c,state):
    global ans
    if r==n and c == n: 
        ans += 1
        return 
    
    if state==0:
        if c < n and graph[r][c+1]==0:
            dfs(r,c+1,0) 
            if r < n and graph[r+1][c]==0 and graph[r+1][c+1]==0: dfs(r+1,c+1,2)
    elif state==1:
        if r < n and graph[r+1][c]==0:
            dfs(r+1,c,1)
            if c < n and graph[r][c+1]==0 and graph[r+1][c+1]==0: dfs(r+1,c+1,2)
    elif state==2:
        if c < n and graph[r][c+1]==0: dfs(r,c+1,0)
        if r < n and graph[r+1][c]==0: dfs(r+1,c,1)
        if c < n and r < n and graph[r+1][c+1]==0 and graph[r+1][c] ==0 and graph[r][c+1] ==0: dfs(r+1,c+1,2)

dfs(0,1,0) 
print(ans)

코드2

• dp로 풀이
• 코드 내용
  • dp는 3중 배열
  • dp[r][c]는 (r,c) 위치에 가로, 세로, 대각선으로 올 수 있는 경우의 수
  • dp의 1행에 대해서는 따로 초기화 / dp 1열에 대해서는 따로 초기화
  • dp의 점화식은 가로/세로/대각선 인 경우에 따라 다르게 작성
    • 가로: dp[r][c][0] = dp[r][c-1][0] + dp[r][c-1][2]
    • 세로: dp[r][c][1] = dp[r-1][c][1] + dp[r-1][c][2]
    • 대각선: dp[r][c][2] = dp[r-1][c-1][0] + dp[r-1][c-1][1] +dp[r-1][c-1][2]

import sys
sys.stdin = open("input.txt", "r") 

n= int(sys.stdin.readline())
graph= [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dp=[[[0 for _ in range(3)] for _ in range(n)]for _ in range(n)]
dp[0][1] = [1,0,0]

for i in range(2,n):
    if graph[1][i]==0:
        dp[0][i][0] = dp[0][i-1][0]

for r in range(1,n):
    for c in range(1,n):
        if graph[r][c]==0:
            dp[r][c][0] = dp[r][c-1][0] + dp[r][c-1][2]
            dp[r][c][1] = dp[r-1][c][1] + dp[r-1][c][2]
            if graph[r][c-1] == 0 and graph[r-1][c]==0:
                dp[r][c][2] = dp[r-1][c-1][0] + dp[r-1][c-1][1] +dp[r-1][c-1][2]

print(sum(dp[n-1][n-1]))