백준_17070_파이프 옮기기 1

문제

17070번: 파이프 옮기기 1

풀이

파이프가 움직일 수 있는 경우의 수를 stack에 넣고 빼내어 연산하였을 때 올바른 답을 얻을 수 있는 것을 확인하였다. 다만, 시간초과로 테스트케이스를 통과하지 못했다.

N = int(input())
board = [list(map(int, input().split())) for i in range(N)]
path = [(0, 1, 0)]  #  end point, 0:→, 1:↘, 2:↓
ans = 0

while path :
    r, c, dir = path.pop(0)
    if [r, c]==[N-1, N-1] : ans+=1

    else :
        if dir == 0 : 
            if c+1<N and r<N and board[r%N][(c+1)%N]==0 :
                path.append((r, c + 1, 0))
            if (c+1<N and r+1<N) and [board[r%N][(c+1)%N], board[(r+1)%N][c%N], board[(r+1)%N][(c+1)%N]]==[0, 0, 0] :
                path.append((r+1, c+1, 1))

        elif dir == 1 : 
            if c+1<N and r<N and board[r%N][(c+1)%N]==0 :
                path.append((r, c + 1, 0))
            if r+1<N and c<N and board[(r+1)%N][c%N]==0 :
                path.append((r+1, c, 2))
            if (c+1<N and r+1<N) and [board[r%N][(c+1)%N], board[(r+1)%N][c%N], board[(r+1)%N][(c+1)%N]]==[0, 0, 0] :
                path.append((r+1, c+1, 1))

        else :  
            if r+1<N and c<N and board[(r+1)%N][c%N]==0 :
                path.append((r+1, c, 2))
            if (c+1<N and r+1<N) and [board[r%N][(c+1)%N], board[(r+1)%N][c%N], board[(r+1)%N][(c+1)%N]]==[0, 0, 0] :
                path.append((r+1, c+1, 1))

print(ans)

해당 문제에 달린 질문을 찾아보다가 아이디어가 떠올랐다. 

문제를 다른 방식으로 표현해보자면, 아래와 같다.

 

모든 파이프는 →,↘,↓세 가지로 표현 할 수 있으며, 특정 위치에 파이프가 세가지 방향으로 놓일 수 있는 경우의 수를 각각 a, b, c라고 표현한다. 주황색 칸의 a, b, c 값을 구하기 위하여 "대각선 위칸", "위칸", "왼쪽칸"을 순서대로 살펴보자.

• 주황색 칸의 ↘ (b)는 "대각선 위칸"의 →,↘,↓(a1, b1, c1)로만 만들 수 있다.
• 주황색 칸의 ↓ (c)는 "위쪽칸"의 ↘,↓(b2, c2)로만 만들 수 있다.
• 주황색 칸의 → (a)는 "왼쪽칸"의 →,↘(a3, b3)로만 만들수 있다.
• (a, b, c) = (a3+b3, a1+b1+c1, b2+c2) 

문제의 조건에 따라 정리해보면, "왼쪽칸"과 "위쪽칸"의 벽의 유무에 관계 없이 움직이는 것이 가능하다. 반면에 "대각선 위쪽칸"의 경우, 왼쪽과 위쪽 어느 쪽에 벽이 있더라도 움직일 수 없다. 

코드

N = int(input())
board = [list(map(int, input().split())) for i in range(N)]

# score은 3차원 배열
# score[i][j]에 →,↘,↓가 위치할 경우의 수를 [a, b, c]처럼 저장
score = [[[0, 0, 0] for j in range(N)] for i in range(N)]
score[0][1][0] = 1 # end point, 0:→, 1:↘, 2:↓

# board[0]의 score setting
for j in range(2, N) :
    if board[0][j] == 0:
        score[0][j][0] = score[0][j - 1][0] + score[0][j - 1][1]  # 옆 노드

# board의 두번째 줄부터 연산 시작
for i in range(1, N) :
    for j in range(2, N) : # board의 첫 두 열은 항상 (0, 0, 0)이므로 세번째열부터 시작
        if board[i][j]==0 :
            score[i][j][0] = score[i][j-1][0] + score[i][j-1][1]    # 옆 노드
            score[i][j][2] = score[i-1][j][1] + score[i-1][j][2]    # 위 노드
            if board[i-1][j]==0 and board[i][j-1]==0 :
                score[i][j][1] = sum(score[i-1][j-1])               # 대각선 위 노드

ans = sum(score[-1][-1])
print(ans)