본문 바로가기
코딩/백준

알고리즘 - Python / 백준 - 17070번 : 파이프 옮기기 1

반응형

17070번: 파이프 옮기기 1 (acmicpc.net)

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

 


풀이

  • 파이프를 움직여 해당 구간까지 옮길 수 있는 방법의 개수를 구하는 문제이다.
  • 현재 파이프의 상태가 가로인지 , 세로인지 , 대각선인지에 따라서 움직일 수 있는 경우가 다르므로 3차원 dp 배열을 통해 각 경우를 구분하고 구분된 경우에 따라서 다음 움직임을 구하도록 하였다.
  • dp[k][i][t] 에서 i와 t는 본래 2차원 dp 배열의 인덱스 , k는 0 일 때 가로 , 1 일 때 세로 , 2일 때 대각선 
  • 현재 가로의 경우 -> 움직일 곳에 벽이 있는지 체크 후 없다면 대각선 / 가로 방향 dp 배열 업데이트
  • 현재 세로의 경우 -> 움직일 곳에 벽이 있는지 체크 후 없다면 대각선 / 세로 방향 dp 배열 업데이트
  • 현재 대각선의 경우 -> 움직일 곳에 벽이 있는지 체크 후 없다면 대각선 / 가로 / 세로 방향 dp 배열 업데이트

 

import sys
n = int(sys.stdin.readline())
stack = []
for _ in range(n):
    stack.append(list(map(int, sys.stdin.readline().split(" "))) + [1])
sub = [1]*(n+1)
stack.append(sub)

dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(3)] #가로 세로 대각
dp[0][0][1] = 1
for i in range(0,n):
    for t in range(0,n):
        for k in range(0,3):
            if dp[k][i][t] > 0:
                if k == 0:
                    if stack[i][t+1] != 1:
                        dp[0][i][t+1] += dp[0][i][t]
                    if stack[i+1][t+1] != 1 and stack[i+1][t] != 1 and stack[i][t+1] != 1:
                        dp[2][i+1][t+1] += dp[0][i][t]
                elif k == 1:
                    if stack[i+1][t] != 1:
                        dp[1][i+1][t] += dp[1][i][t]
                    if stack[i+1][t+1] != 1 and stack[i+1][t] != 1 and stack[i][t+1] != 1:
                        dp[2][i+1][t+1] += dp[1][i][t]
                elif k == 2:
                    if stack[i][t + 1] != 1:
                        dp[0][i][t+1] += dp[2][i][t]
                    if stack[i + 1][t + 1] != 1 and stack[i+1][t] != 1 and stack[i][t+1] != 1:
                        dp[2][i+1][t+1] += dp[2][i][t]
                    if stack[i + 1][t] != 1:
                        dp[1][i+1][t] += dp[2][i][t]

if stack[n-1][n-1] == 1:
    print(0)
else:
    print(dp[0][n-1][n-1] + dp[2][n-1][n-1] + dp[1][n-1][n-1])

 

 

 

반응형