백준 17070 파이프 옮기기 1

백준 17070번 문제 바로가기

문제 이해

총 세가지 상태(state)가 있다.

각각 a, b, c라고 했을때 움직일 수 있는 경우의수는 다음과 같다.

보통 이런 경우 현재 상태를 기준으로 다음 움직임을 판단한다.

if 0: 
    check(0), move(0)
    check(1), move(1)
if 1: 
    check(1), move(1)
    check(2), move(2)
if 2: 
    check(0), move(0)
    check(1), move(1)
    check(2), move(2)

하지만 이렇게 할 경우 매 움직임마다 조건(벽에 부딪히는지)을 확인해야 하기 시간이 상당히 소요되며 코드도 중복된다. 이를 극복하기 위해 약간 반대로 생각해서 특정 move()가 가능한 모든 state를 기준으로 잡는다.

if 0,1:
	check(0), move(1)
if 0,2
	check(1), move(1)

코드

import sys
N = int(sys.stdin.readline())
board = [ list(map(int, sys.stdin.readline().split())) for _ in range(N)]

counts = []
def move(point, state):
    if point== (N-1,N-1):
        counts.append(1)
        return
    
    x,y = point
    if state in [0,2]:
        if x+1 < N and board[y][x+1] ==0: 
            move((x+1,y), 0)
    
    if state in [1,2]:
        if  y+1 <N and board[y+1][x] ==0:
            move((x,y+1),1)
    
    if state in [0,1,2]:
        if x+1< N and y+1 <N:
            if board[y][x+1]==0 and board[y+1][x]==0 and board[y+1][x+1]==0:
                move((x+1,y+1),2)


start = (1,0) # x,y
move(start,0)
print(sum(counts))