소프티어

DFS 가지치기 잘하면 괜찮다고 하길래 중복 제거하려고 시점,방향,위치 고려한 가지치기 진행했는데도 여전히 시간 초과가 발생하네요.

오래 생각해봤는데도 이유를 잘 모르겠습니다.

혹시 짐작 가는 부분이 있으신 분이 계신가요?

import sys

def dfs(depth, si, sj, sd, visited): # visited 관리 [i,j,d,t]: t시간에 (i,j)위치를 향해 d방향으로 들어옴
  global global_visited
  if depth == T:
    global_visited.extend(visited)
    return

  rotary_key = arr[si][sj][depth%4]
  rotary_val = rotaryType[rotary_key]

  if rotary_val[0] == sd:
    flag = 0
    for d in rotary_val[1]:
      ni, nj = si+di[d], sj+dj[d]
      if 0<=ni<N and 0<=nj<N and (ni,nj,d,(depth+1)%4) not in global_visited:
        flag = 1
        visited.append((ni,nj,d,(depth+1)%4))
        dfs(depth+1, ni, nj, d, visited)
        visited.remove((ni,nj,d,(depth+1)%4))
    if flag == 0:
      global_visited.extend(visited)
      return
  else:
    global_visited.extend(visited)
    return


# 상0 우1 하2 좌3
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

rotaryType = {
  1 : [1,[0,1,2]], # [입력방향 인덱스, [출력방향 인덱스]]
  2 : [0,[3,0,1]],
  3 : [3,[2,3,0]],
  4 : [2,[1,2,3]],
  5 : [1,[0,1]],
  6 : [0,[3,0]],
  7 : [3,[2,3]],
  8 : [2,[1,2]],
  9 : [1,[1,2]],
  10: [0,[0,1]],
  11: [3,[3,0]],
  12: [2,[2,3]]
}

N, T = map(int, input().split())
arr = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(N):
    tmp = list(map(int, input().split()))
    arr[i][j] = tmp

global_visited = []
dfs(0, 0, 0, 0, [(0,0,0,0)]) # [i,j,d,t]

result = []
for i,j,d,t in global_visited:
  if (i,j) not in result:
    result.append((i,j))
print(len(result))