[백준 17070번] 파이프 옮기기 1 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())

graph = []
for i in range(N):
  graph.append(list(map(int,input().split())))


count = 0

def DFS(y,x,state):
  global count
  if y==x==N-1:      #도착시 개수 세기
    count += 1
    return
  if state == 0:    #가로일때
    if x+1<N:
      if graph[y][x+1]==0:
        DFS(y,x+1,0)
    if x+1<N and y+1<N:
      if graph[y][x+1]==0 and graph[y+1][x]==0 and graph[y+1][x+1]==0:
        DFS(y+1,x+1,1)
  elif state == 1:    #대각선일때
    if x+1<N:
      if graph[y][x+1]==0:
        DFS(y,x+1,0)
    if x+1<N and y+1<N:
      if graph[y][x+1]==0 and graph[y+1][x]==0 and graph[y+1][x+1]==0:
        DFS(y+1,x+1,1)
    if y+1<N:
      if graph[y+1][x]==0:
        DFS(y+1,x,2)
  else:              #세로일때
    if x+1<N and y+1<N:
      if graph[y][x+1]==0 and graph[y+1][x]==0 and graph[y+1][x+1]==0:
        DFS(y+1,x+1,1)
    if y+1<N:
      if graph[y+1][x]==0:
        DFS(y+1,x,2)


DFS(0,1,0)
print(count)

고전적인 DFS 방식으로 해결했다. 다만 python3로는 시간초과가 발생하여 pypy3로 제출해서 통과하였다.

 

다른 사람들 풀이를 참고하니 python3로 통과하기 위해서는 DP 방식을 이용해야 하는것 같다.

 

 

오늘의 교훈) 데이터가 크면 DP 방식을 이용하자