백준 17070 파이프 옮기기 1 / python

문제 : 17070

풀이 point

dp를 활용하는 문제이다. 파이프의 끝 부분에서 가로, 세로, 대각선으로 진행될 수 있다. 파이프의 끝 부분을 통해 가로, 세로, 대각선의 방법을 3차원 dp에 저장해나가며 진행하면 된다.

풀이 방법

우선 초기 설정이 필요하다. 맨 위 행의 경우 파이프가 가로로 올 수 있다. 그렇기 때문에 벽을 제외한 모든 부분을 갱신해주면 된다. 그 다음 맨 첫 열은 파이프가 올 수 없다.(가로 시작이라)

본격적으로 진행해보자면, 파이프의 끝 부분에서 그 전 파이프에 상태에 따라 가로, 세로, 대각선으로 진행될 수 있는지 여부가 달라진다. 예를들면

(모든 경우는 현재 칸이 벽이 아니어야 함)
가로의 경우 : 그전 파이프가 가로 혹은 대각선이어야 가능하다.
세로의 경우 : 그전 파이프가 세로 혹은 대각선이어야 가능하다.
대각선의 경우 : 그전 파이프가 가로, 세로 혹은 대각선이어야 가능하다.(단, 위, 왼쪽 같이 벽이 아니어야 함)

이렇게 경우를 나누어서 그전 파이프의 dp 값으로 부터 경우의 수를 계산할 수 있다.

풀이 코드

N = int(input())

grid = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0]*3 for _ in range(N)] for _ in range(N)]
# [0] = 가로, [1] = 세로, [2] = 대각선

# 가로 설정
dp[0][1][0] = 1
for i in range(2, N):
  if grid[0][i] == 0:
    dp[0][i][0] = dp[0][i-1][0]
  else:
    break

for i in range(1, N):
  for j in range(1, N):
    if grid[i][j]:
      continue
    
    dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2] #가로 = 가로 + 대각선
    dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2] #세로 = 세로+대각선
    
    if not grid[i][j-1] and not grid[i-1][j]: 
      dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2] #대각선 = 가로+세로+대각선

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

사족

처음에는 bfs로 모든 경우의 수를 탐색하면 되는거 아닌가 생각했다. 다만 시간초과가 날 것같아서 dp라고 생각을 고쳤는데, 막상 다른분들의 풀이를 보니 경우의 수를 모두 진행하는 bfs도 가능한 것 같다.

경우의 수가 3개이니 지수적으로 늘어날 것이라 생각했으나 어쨌든 경우의 수는 이미 그 전에 구해놓은 함수가 있을 수 있으니(갈 수 있는 방향은 한정적으로 N^2 범위니깐) 메모이제이션을 쓰면 되는 것이었다...!