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

문제

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

---

[사용한 알고리즘]

• 다이나믹 프로그래밍
• 시뮬레이션

[풀이]

본 문제는 다이나믹 프로그래밍을 이용하면 쉽게 풀 수 있다. 그와 동시에 시뮬레이션 문제이므로 구현해야 하는 바를 잘 구현하여 풀도록 하자.

문제의 조건은 다음과 같다.

1. 처음에 설치된 파이프는 (1,1) (1,2) 에 위치하며 방향은 가로이다.
2. 각 파이프가 설치된 모양에 따라 회전할 수 있는 방향이 결정된다.
3. 회전 방향에 따른 공간이 비어있어야 한다.

알고리즘 설명

1. dictionary 를 이용하여 각 방향의 회전 방향을 저장해둔다. ( 가로모양 : 0 , 대각선 모양 : 1 , 세로모양 : 2)
2. cos 에는 방향에 따른 증가하는 dy, dx 를 저장한다.
3. dp 테이블 ( 코드에서는 count ) 를 3차원 배열로 저장하여 dp[y][x][0, 1, 2] 에 각각 방향에 따른 경우의 수를 저장한다.
4. dp 테이블에 값이 있다면 check함수를 실행한다. ( dp[y][x][0] == 0 이라면 y행x열에 해당하는 위치에 가로모양으로 파이프가 놓일 수 없었음을 의미하기에 check를 실행하지 않는다.)
5. check 함수는 문제의 조건에 맞는 행동을 수행한다.

코드

import sys
from collections import deque
input = sys.stdin.readline

RIGHT_STRAIGHT = 0
DIAGONAL_STRAIGHT = 1
DOWN_STRAIGHT = 2

def check(y,x,d):
    for direction in directions[d]:
        dy, dx = cos[direction]
        ny = y + dy
        nx = x + dx
        if ny < N and nx < N and not m[ny][nx]:
            if direction != 1:
                count[ny][nx][direction] += count[y][x][d]
            else:
                if not m[ny - 1][nx] and not m[ny][nx - 1]:
                    count[ny][nx][direction] += count[y][x][d]

N = int(input())
m = [ list(map(int,input().split())) for _ in range(N)]
count = [ [ [0] * 3 for _ in range(N) ] for _ in range(N)]

# 0 : 오른쪽 1 : 대각선 2: 아래
directions = { 0 : [0,1] , 1 : [0,1,2] , 2: [1,2]}
cos = {0 : [0,1] , 1 : [1,1] , 2: [1,0]}

count[0][1][0] = 1

for i in range(N):
    for j in range(N):
        for d in range(3):
            if count[i][j][d] and not m[i][j]:
                check(i,j,d)

print(sum(count[N-1][N-1]))