[백준] 17070 파이프 옮기기1 (Python/파이썬)

<문제링크>

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

17070번: 파이프 옮기기 1

 

<풀이 전략>

1. 2차원 배열에서 도착지까지의 경로의 개수를 찾는 유형의 DP 문제이지만 N의 범위가 작아 BFS로도 풀 수 있습니다.

2. 저는 DP로 풀었으며 테이블은 각 좌표마다 해당 좌표를 끝점으로 하는 파이프가 놓일 수 있는 경우의 수를 각 방향(가로, 세로, 대각선)에 대해 계산한 배열로 정의했습니다.

3. 해당 좌표와 직전 좌표의 벽 여부를 검사하면서 테이블을 채워 나가면 됩니다.

 

<정답 코드>

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 230404 17070 파이프 옮기기

# 정답코드

N = int(input())

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

dp = [[[0, 0, 0] for _ in range(N)] for _ in range(N)] # 가로, 세로, 대각선

for r in range(N):
    for c in range(1, N):

        # 벽
        if arr[r][c] == 1:
            continue

        # 첫 행
        if r == 0:
            # 초기위치
            if c == 1:
                dp[r][c][0] = 1
                continue

            # 가로
            if arr[r][c - 1] == 0:
                dp[r][c][0] += dp[r][c - 1][0] + dp[r][c - 1][2]
            #대각
            if arr[r - 1][c - 1] == 0 and arr[r][c - 1] == 0 and arr[r - 1][c] == 0:
                dp[r][c][2] += dp[r - 1][c - 1][0] + dp[r - 1][c - 1][1] + dp[r - 1][c - 1][2]



        if 0 <= r - 1:
            # 가로
            if arr[r][c - 1] == 0:
                dp[r][c][0] += dp[r][c - 1][0] + dp[r][c - 1][2]
            #세로
            if arr[r - 1][c] == 0:
                dp[r][c][1] += dp[r - 1][c][1] + dp[r - 1][c][2]
            #대각
            if arr[r - 1][c - 1] == 0 and arr[r][c - 1] == 0 and arr[r - 1][c] == 0:
                dp[r][c][2] += dp[r - 1][c - 1][0] + dp[r - 1][c - 1][1] + dp[r - 1][c - 1][2]



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