BOJ 2210번: 숫자판 점프

https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

DFS와 브루트포스를 이용하여 풀 수 있는 문제였다.

주어진 숫자판의 모든 원소를 시작점으로 하여 해당 시작점의 인덱스를 DFS 함수의 변수로 주었다. DFS 함수 안에서는 가능한 방향으로 움직여 다시 DFS 를 재귀 호출하였고, 움직인 횟수가 5가되면 만들어진 문자열을 ans 배열에 추가한 후 리턴하였다. 이때 인덱스 오류가 나지 않도록 체크해주어야 한다.

 

import sys
input = sys.stdin.readline

def dfs(x, y):
    global cnt, tmp
    tmp = tmp[:cnt] + arr[x][y]
    
    if (cnt==5):
        ans.append(tmp)
        return
    
    if (x+1<5):
        cnt += 1
        dfs(x+1, y)
        cnt -= 1
        
    if (x-1>=0):
        cnt += 1
        dfs(x-1, y)
        cnt -= 1
        
    if (y+1<5):
        cnt += 1
        dfs(x, y+1)
        cnt -= 1
        
    if (y-1>=0):
        cnt += 1
        dfs(x, y-1)
        cnt -= 1
        
arr = []

for _ in range(5):
    arr.append(list(input().split()))
ans = []
tmp = '......'
        
for i in range(5):
    for j in range(5):
        cnt = 0
        dfs(i,j)
ans =set(ans)
print(len(ans))