백준(Python) 17070번 파이프 옮기기 1 풀이

Python으로 구현한 17070번 파이프 옮기기 1 문제 풀이입니다.

 

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

17070번: 파이프 옮기기 1

---

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

# 0: 가로, 1: 세로, 2: 대각선
dp = [[[0] * n for _ in range(n)] for _ in range(3)]

dp[0][0][1] = 1 # 첫시작 (가로, (0, 1) 좌표)
# 첫 행 초기화
for i in range(2, n) :
    if data[0][i] == 0 :
        dp[0][0][i] = dp[0][0][i-1]

for x in range(1, n) :
    for y in range(1, n) :
        # 대각선
        if data[x][y] == 0 and data[x-1][y] == 0 and data[x][y-1] == 0 :
            dp[2][x][y] = dp[0][x-1][y-1] + dp[1][x-1][y-1] + dp[2][x-1][y-1]

        if data[x][y] == 0 :
            # 가로
            dp[0][x][y] = dp[0][x][y-1] + dp[2][x][y-1]
            # 세로
            dp[1][x][y] = dp[1][x-1][y] + dp[2][x-1][y]

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

 

1. 각 가로, 세로, 대각선으로 이동한 정보를 포함한 dp 리스트를 정의한 후 첫 시작은 (0, 1)좌표에서 가로로 시작하므로 dp[0][0][1]을 1로 갱신한다.

 

2. dp를 사용하기 위해 반복문을 통해 첫 행을 초기화해준다.

 

3. (1, 1) 좌표부터 dp 값을 갱신해나가는데, 해당 작업은 아래와 같이 수행한다.

  - 만약 data[x][y]의 값이 0이고 data[x-1][y] 값이 0이고 data[x][y-1] 값이 0일 경우 대각선 방향으로 이동할 수 있으므로

    dp[2][x][y]에 가로로 온 이전 방법의 개수 + 세로로 온 이전 방법의 개수 + 대각선으로 온 이전 방법의 개수를 더하여 저장한다.

  - 만약 data[x][y]가 0(빈 칸)이고, 현재 위치가 가로인 경우 가로로 온 이전 방법의 개수 + 대각선으로 온 이전 방법의 개수를 더하여 저장한다.

  - 만약 data[x][y]가 0(빈 칸)이고, 현재 위치가 세로인 경우 세로로 온 이전 방법의 개수 + 대각선으로 온 이전 방법의 개수를 더하여 저장한다.

 

4. 최종적으로 (n-1, n-1) 좌표에 이동시키는 방법의 수를 모두 더한 값을 출력한다.