이번 문제는 깊이우선탐색을 통해 해결하였다. 거쳤던 곳을 다시 방문해도 상관없기 때문에 방문 처리를 따로 하지 않았고, 4방향으로 모두 재귀호출하여 문자열의 길이가 6이 되었을 때 정답 리스트에서의 중복 검사를 거쳐 삽입하는 방식으로 접근하였다.

• 재귀 제한을 늘려준다.
• dfs함수를 h, w, tmp를 인자로 갖도록하여 선언한다.
  -> 만약 tmp의 길이가 6일 경우,
  --> 만약 nums에 tmp가 없을 경우 nums에 tmp를 삽입한다.
  --> 함수를 종료한다.
  -> 4가지 방향을 저장하기 위해 dh, dw를 선언하고 짝을 지어 삽입한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> 다음 인덱스를 저장할 임시 변수 next_h, next_w를 선언하고 h+dh[i], w+dw[i]를 저장한다.
  --> 만약 next_h, next_w가 0보다 크고 next_h, next_w가 5보다 작을 경우 dfs(next_h, next_w, tmp+pad[next_h][next_w])를 재귀호출한다.
• 숫자판을 저장할 리스트 pad를 선언한다.
• 5번 반복하는 for문을 돌린다.
  -> pad를 문자열 타입으로 입력한다.
• 만들 수 있는 수를 담을 리스트 nums를 선언한다.
• 5번 반복하는 i에 대한 for문을 돌린다.
  -> 5번 반복하는 j에 대한 for문을 돌린다.
  --> dfs(i, j, pad[i][j])를 호출한다.
• nums의 길이를 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(h, w, tmp):
    if len(tmp)==6:
        if tmp not in nums:
            nums.append(tmp)
        return
    dh = [0, 0, 1, -1]
    dw = [1, -1, 0, 0]
    for i in range(4):
        next_h=h+dh[i]
        next_w=w+dw[i]
        if next_h>=0 and next_w>=0 and next_h<5 and next_w<5:
            dfs(next_h, next_w, tmp+pad[next_h][next_w])
pad=[]
for _ in range(5):
    pad.append(list(map(str, input().split())))
nums=[]
for i in range(5):
    for j in range(5):
        dfs(i, j, pad[i][j])
print(len(nums))