문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

import sys

input = sys.stdin.readline

from collections import deque

graph = []
for _ in range(5):
  graph.append(list(input().split()))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

numbers = []


def bfs(x, y, number="", count=0):
  queue = deque()
  queue.append((x, y, number, count))
  while queue:
    x, y, number, count = queue.popleft()
    number += graph[y][x]
    count += 1
    if count == 6:
      if number in numbers:
        continue
      else:
        numbers.append(number)
      continue
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx > 4 or ny > 4:
        continue
      queue.append((nx, ny, number, count))


for i in range(5):
  for j in range(5):
    bfs(i, j)

print(len(numbers))

백준 2210 숫자판 점프