[BOJ/Python] 백준 2210번 - 숫자판 점프

백준 #2210 숫자판 점프

2210번: 숫자판 점프

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

grid = [list(map(int, input().split())) for _ in range(5)]
num_set = set()   # 서로 다른 여섯 자리의 수들의 집합

def dfs(i, j, num):
  num += str(grid[i][j])
  if len(num) == 6:
    num_set.add(num)
    return
  for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
    x, y = i + dx, j + dy
    if 0 <= x < 5 and 0 <= y < 5:
      dfs(x, y, num)

for i in range(5):
  for j in range(5):
    dfs(i, j, '')

print(len(num_set))

방문한 곳을 표시할 필요도 없는 완전한 브루트포스 문제. 시작 정점을 [0][0] 부터 [4][4] 까지 해서 깊이 우선 탐색을 하면 끝이다. 탐색하다 숫자열 길이가 6이 되면 해당 숫자열을 집합 안에 저장하여 같은 숫자열이 또 저장되지 않도록 한다. dfs를 끝내고 집합 내에 저장 돼 있는 숫자열 개수를 출력하면 끝!