[백준 17070번] 파이프 옮기기 1 - python

문제 링크

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

17070번: 파이프 옮기기 1

풀이

- dp로 풀었다. 

dp 는 3차원 배열로 두고, 

dp[0]은 현재 위치가 가로 일 때 경우의수

dp[1]은 현재 위치가 세로 일 때 경우의 수

dp[2]은 현재 위치가 대각선일 때 경우의 수 이다. 

1. 현재 파이프가 (0,0) (0,1)에 가로로 위치해 있으므로

dp[0][0][1] 은 1로 초기화

 

2. 첫번째 줄은 가로로 밖에 올 수 없으므로 

dp[0][0][i] = dp[0][0][i-1]로 초기화 

 

3. 두번째 줄, 두번째 칸부터 

1) 현재 위치가 대각선이라면 

가로에서 대각선으로 오는 방법 + 세로에서 대각선으로 오는 방법 + 대각선에서 대각선으로 오는 방법
dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1]

 

2) 현재 위치가 세로라면

세로에서 세로로 오는 방법 + 대각선에서 세로로 오는 방법
dp[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j]

 

3) 현재 위치가 가로라면 

 가로에서 가로로 오는 방법 + 대각선에서 가로로 오는 방법 
dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1]

 

4. answer에는 

dp[0][n-1][n-1] + dp[1][n-1][n-1] + dp[2][n-1][n-1] 대입하여 출력 

import sys
input = sys.stdin.readline 

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

# 가로 : 0 , 세로 : 1, 대각선 : 2    
dp = [ [[0] * n for _ in range(n)] for _ in range(n) ] 

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 i in range(1,n):
    # 파이프가 (1,1)와 (1,2)를 차지하고 있으므로 두번째 칸부터 가능 
    for j in range(2,n):
        # 현재 위치가 대각선일 때 
        if graph[i][j] == 0 and graph[i-1][j] == 0 and graph[i][j-1] == 0:
            # 가로에서 대각선으로 오는 방법 + 세로에서 대각선으로 오는 방법 + 대각선에서 대각선으로 오는 방법
            dp[2][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[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j]
            # 가로 일 때 = 가로에서 가로로 오는 방법 + 대각선에서 가로로 오는 방법 
            dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1]
            
answer = 0 
for i in range(3):
    answer += dp[i][n-1][n-1]
    
print(answer)

- 그래프 문제를 bfs, dfs, dp로 3가지 방법으로 풀 수 있도록 연습을 많이 해봐야겠다