백준 17069번 파이프 옮기기2

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

17069번: 파이프 옮기기 2

 

 

분명 BFS로 파이프 옮기기1은 BFS로 풀 수 있는 문제라고 하셨는데...... 결국 DP로 접근해서 풀고,

 

DP로 풀었으니, 파이프 옮기기2도 가뿐하게 풀 수 있었기에 뿌듯했습니다.

 

하지만 DP로 어떻게 접근해야 할 지 생각하느라 잠을 설친걸 생각하면.. 아직 멀었다는 생각이 듭니다

 

그래도 혼자 생각해낸게 어디냐며 굉장히 뿌듯하게 풀은 문제입니다.

 

** 소스코드는 더보기를 클릭해서 확인해주세요 **

 

 

1. DP 접근의 시작

• ㅡ 모양은 0, \ 모양은 1, ㅣ 모양은 2의 상태로 두었습니다.
• 0에서는 0과 1로 갈 수 있지만 2로 갈 수 없고, 1은 0과 1 2 모두 갈 수 있고, 2는 2와 1로 갈 수 있습니다
• 처음엔 무턱대고 이전 값의 경우의수를 체크하여 더해주려고 했지만 이전 값의 경우의수가 있더라도 내 칸으로 올 수 없다는 경우가 발생한다는 걸 깨달았습니다. (내 왼쪽에 파이프가 올 수 있는 경우의 수가 있지만 그 파이프의 상태가 2라면? 오른쪽으로는 못오잖아..?) 
• 그래서 파이프의 상태까지 담아줄 방법을 고민하게 됩니다.

 

N = int(input())

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

#경우의수를 담아줄 memo리스트 추가
#그냥 경우의수를 체크하는게 아니라 어떤 상태로 현재 값으로 올 수 있는지를 체크해야한다
# 왜냐면 현재 값에서 0상태로 몇개 1상태로 몇개 2상태로 몇개 올 수 있는지 체크해야만
# 현재값으로 올 수 없는 경우의수가 있기 때문
# i, j좌표에 각 상태별 경우의수를 담는 배열이 하나더 필요하므로 i,j,k 세개의 배열이 필요할 것 같다

memo = [[[0] * 3 for _ in range(N)] for _ in range(N)]

for c in range(N-1): #첫째줄에는 모두 0상태로 들어갈 수 있음
    if board[0][c+1] != 1 :
        memo[0][c+1][0] += 1
    else :
        break

 

 

2. 각 칸에 올 수 있는 조건 확인하기

• 다시 처음으로 돌아가 생각해보았는데, 생각해보니 첫 번째 줄에 파이프가 ㅡ 모양(0상태)으로밖에 들어가지 못한다는걸 발견합니다.
• 그것을 발견하고 나니 2번째 칸에는 \(1)모양으로밖에 갈 수 없다는 것도 보이구요
• 또 보니까, 0열과 1열은 첫째줄을 제외하면 사용하지도 못합니다.
• 아!! 각 상태별로 조건들이 보입니다
• 각 칸은 올 수 있는 상태가 정해져있고, 또 1번 상태의 경우에는 이동할 칸의 위와 왼쪽이 비어있어야합니다.
• 모든 조건들을 다 적어주도록 합니다. (1부터 시작할 것이기 때문에 사실 2, 3번째 조건은 필요 없는 조건이긴 하지만요)

# 다음부터는 내 왼쪽과, 위, 그리고 왼쪽 위의 값에 따라 자동으로 경우의수가 증가
for i in range(1, N):
    for j in range(1, N):
        if board[i][j] == 0:
            #왼쪽 위가 존재하는데 상태가 0,1,2이라면 1상태로 올 수 있음
            #단 1상태로 오려면 무조건 올 수 있는게 아니라 위와 왼쪽 공간이 비어있어야함
            if 0 <= i -1 < N and 0 <= j -1 < N and board[i-1][j] == 0 and board[i][j-1] == 0:
                pass
            #위가 존재하는데 1이나 2상태라면 2로 올 수 있음
            if 0 <= i -1 < N :
                pass
            #왼쪽이 존재하는데 0이나 1상태라면 0으로 올 수 있음
            if 0 <= j -1 < N :
                pass

 

3. 경우의수 체크

• 이제 각 칸들이 들어올 수 있는 조건들을 체크해주었으니 상태값에 따른 경우의수를 넣어주어야 합니다.
• 만약 왼쪽 칸에 파이프가 올 수 있는 경우의 수가 존재했더라도 그 파이프가 2상태라면 올 수 없으니까요.
• 모든 칸의 경우의수를 상태별로 나누어 놓았으니 내 칸으로 올 때 어떤 상태로 오는지도 같이 넣어줍니다.
• 파이프가 왼쪽에 있다면 0가 1상태인 파이프가 0상태인 파이프로 변해서 제 자리로 올 수 있을것이고
• 파이프가 왼쪽위에 있다면 0, 1, 2상태의 파이프가 1상태인 파이프로 변해서 올 수 있을 것이고
• 파이프가 위에 있다면 1과 2상태의 그래프가 2상태인 파이프로 변해서 올 수 있겠죠

# 다음부터는 내 왼쪽과, 위, 그리고 왼쪽 위의 값에 따라 자동으로 경우의수가 증가
for i in range(1, N):
    for j in range(1, N):
        if board[i][j] == 0:
            #왼쪽 위가 존재하는데 상태가 0,1,2이라면 1상태로 올 수 있음
            #단 1상태로 오려면 무조건 올 수 있는게 아니라 위와 왼쪽 공간이 비어있어야함
            if 0 <= i -1 < N and 0 <= j -1 < N and board[i-1][j] == 0 and board[i][j-1] == 0:
                memo[i][j][1] += memo[i-1][j-1][0] + memo[i-1][j-1][1] + memo[i-1][j-1][2]
            #위가 존재하는데 1이나 2상태라면 2로 올 수 있음
            if 0 <= i -1 < N :
                memo[i][j][2] += memo[i-1][j][1] + memo[i-1][j][2]
            #왼쪽이 존재하는데 0이나 1상태라면 0으로 올 수 있음
            if 0 <= j -1 < N :
                memo[i][j][0] += memo[i][j-1][0] + memo[i][j-1][1]

이제 마지막 칸까지 도착한 상태별 경우의수를 모두 더해주면 답이 됩니다.

 

전체 코드

 

N = int(input())

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

#경우의수를 담아줄 memo리스트 추가
#그냥 경우의수를 체크하는게 아니라 어떤 상태로 현재 값으로 올 수 있는지를 체크해야한다
# 왜냐면 현재 값에서 0상태로 몇개 1상태로 몇개 2상태로 몇개 올 수 있는지 체크해야만
# 현재값으로 올 수 없는 경우의수가 있기 때문
# i, j좌표에 각 상태별 경우의수를 담는 배열이 하나더 필요하므로 i,j,k 세개의 배열이 필요할 것 같다

memo = [[[0] * 3 for _ in range(N)] for _ in range(N)]

for c in range(N-1): #첫째줄에는 모두 0상태로 들어갈 수 있음
    if board[0][c+1] != 1 :
        memo[0][c+1][0] += 1
    else :
        break

# 다음부터는 내 왼쪽과, 위, 그리고 왼쪽 위의 값에 따라 자동으로 경우의수가 증가
for i in range(1, N):
    for j in range(1, N):
        if board[i][j] == 0:
            #왼쪽 위가 존재하는데 상태가 0,1,2이라면 1상태로 올 수 있음
            #단 1상태로 오려면 무조건 올 수 있는게 아니라 위와 왼쪽 공간이 비어있어야함
            if 0 <= i -1 < N and 0 <= j -1 < N and board[i-1][j] == 0 and board[i][j-1] == 0:
                memo[i][j][1] += memo[i-1][j-1][0] + memo[i-1][j-1][1] + memo[i-1][j-1][2]
            #위가 존재하는데 1이나 2상태라면 2로 올 수 있음
            if 0 <= i -1 < N :
                memo[i][j][2] += memo[i-1][j][1] + memo[i-1][j][2]
            #왼쪽이 존재하는데 0이나 1상태라면 0으로 올 수 있음
            if 0 <= j -1 < N :
                memo[i][j][0] += memo[i][j-1][0] + memo[i][j-1][1]

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