[백준] 17070번 : 파이프 옮기기 1 (파이썬/python) 그래프탐색/dp

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

17070번: 파이프 옮기기 1

 

이거 DP로도 풀수있다는데 방법의 수가 1억개 보다는 작으니까

그래프 구현으로 풀었다 

n = int(input())
array = []
answer = 0 
dp = [[0] * n for _ in range(n)]
for i in range(n):
    array.append(list(map(int, input().split())))
    

def move(x1, y1, x2, y2, type):
    global answer
    if (x1 == n-1 and y1 == n-1) or (x2 == n-1 and y2 == n-1):
        # dp 그래프 
        answer += 1
        return 
    
    if type == 0:
        # 가로 방향 
        if 0 <= x2 < n and 0 <= y2+1 < n:
            if array[x2][y2+1] == 0:
                move(x2, y2, x2, y2+1, 0)
            
        # 대각선 
        if 0 <= x2+1 < n and 0 <= y2+ 1 < n:
            if array[x2+1][y2+1] == 0 and array[x2+1][y2] == 0 and array[x2][y2+1] == 0:
                move(x2, y2, x2+1, y2+1, 2)
                
    elif type == 1: # 세로방향
        if  0 <= x2+1 < n and 0 <= y2 < n:
            if array[x2+1][y2] == 0:
                move(x2, y2, x2+1, y2, 1)
        
        if 0 <= x2+1 < n and 0 <= y2+1 < n:
            if array[x2+1][y2+1] == 0 and array[x2+1][y2] == 0 and array[x2][y2+1] == 0:              
                move(x2, y2, x2+1, y2+1, 2) 
    elif type == 2: # 대각선 
        if 0 <= x2 < n and 0 <= y2+1 < n:
            if array[x2][y2+1] == 0:
                move(x2, y2, x2, y2+1, 0)
            
        if  0 <= x2+1 < n and 0 <= y2 < n:
            if array[x2+1][y2] == 0:
                move(x2, y2, x2+1, y2, 1)
        
        if 0 <= x2+1 < n and 0 <= y2+1 < n:
            if array[x2+1][y2+1] == 0 and array[x2+1][y2] == 0 and array[x2][y2+1] == 0:
                move(x2, y2, x2+1, y2+1, 2) 
move(0, 0, 0, 1, 0)

print(answer)

 

DP를 이용한 풀이는 다음과 같다. 다른 블로그에서 참고했다

# dp 풀이 
import sys 
input = sys.stdin.readline 

graph = []
n = int(input())
for i in range(n):
    graph.append(list(map(int, input().split())))
    
dp = [[[0] * n for _ in range(n)] for _ in range(3)] 
# dp[0][row][col] = 가로 파이프에 대한 dp 
# dp[1][row][col] = 대각선 파이프에 대한 dp 
# dp[2][row][col] = 세로 파이프에 대한 dp 

# 첫행은 가로 파이프대로만 이동가능함. 
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]

# 1행을 제외하고 부터 dp 시작 
for i in range(1, n):
    for j in range(1, n):
        # 대각선 방향 이동하기 
        if graph[i][j] == 0 and graph[i-1][j] == 0 and graph[i][j-1] == 0:
            dp[1][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1]
            
        # 가로 세로 방향 
        if graph[i][j] == 0:
            # 가로 : 가로 & 대각선에서 올 수 있음 
            dp[0][i][j] = dp[0][i][j-1] + dp[1][i][j-1]
            
            dp[2][i][j] = dp[2][i-1][j] + dp[1][i-1][j]

print(dp[0][n-1][n-1] + dp[1][n-1][n-1] + dp[2][n-1][n-1])