[백준/Python] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

문제에 제시된 그림을 보면, 답을 구할 수 있는 힌트가 있다. 다음과 같이 경우를 나눠볼 수가 있다.

 

가로로 오는 경우 -> 가로에서 가로로, 대각선에서 가로로

세로로 오는 경우 -> 세로에서 세로로, 대각선에서 세로로

대각선으로 오는 경우 -> 가로에서 대각선으로, 세로에서 대각선으로, 대각선에서 대각선으로

 

이것을 기반하여 DP를 활용하여 코드를 작성하면 된다. 가로, 세로, 대각선 총 3가지 경우가 있으므로 3차원리스트를 사용하여 문제를 풀어야 한다.

 

 

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[[0] * n for _ in range(n)] for _ in range(3)] # 0: 가로, 1: 세로, 2: 대각선
dp[0][0][1] = 1 # 처음 위치 초기화

# 0번째 행 초기화
for j in range(2, n):
    if board[0][j] == 0:
        dp[0][0][j] = dp[0][0][j-1]

for i in range(1, n):
    for j in range(1, n):
        # 대각선인 경우
        if board[i][j] == 0 and board[i-1][j] == 0 and board[i][j-1] == 0:
            dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1]
        # 가로, 세로인 경우
        if board[i][j] == 0:
            dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1] # 가로
            dp[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j] # 세로

print(sum([dp[i][n-1][n-1] for i in range(3)]))

1. 가로, 세로, 대각선의 경우를 저장할 3차원 리스트인 dp를 생성한다. dp[0][i][j] 에는 가로, dp[1][i][j] 에는 세로, dp[2][i][j] 에는 대각선인 경우의 수를 저장할 것이다.

2. 처음 위치를 초기화해준다. 가로로 놓이며 파이프 끝이 (0, 1)에 위치하므로 dp[0][0][1] = 1로 초기화한다.

3. 0번째 행은 가로로 오는 경우 밖에 없으므로 먼저 초기화해준다. 이 때, dp[0][0][j] = 1로 하면 안된다!! 만약에 이전 위치에서 벽인 경우 파이프를 놓을 수 없는데, 1로 초기화하면 벽을 뚫고 파이프를 놓는 것이 된다. 따라서 이전 위치의 dp 값을 가져와 초기화해줘야 된다.

4. 전체 board를 탐색하면서 경우의 수를 구한다. 위에서 생각해보았던 경우에 따라서 대각선, 가로, 세로를 각각 다르게 처리해준다.

5. 마지막으로 (n-1, n-1) 위치의 경우의 수를 출력한다.