#380 백준 파이썬 [2210] 숫자판 점프 - DFS

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

 

SOLUTION

0,0 부터 4,4 까지 모든 출발점에 대하여 DFS(깊이우선탐색)을 실행시켜주는 문제다.

들어오는 입력과 숫자들을 모두 str취급해주어(0또한 숫자로 취급되기에) 6글자가 될 때까지 재귀해준다.

왔던 길을 다시 돌아갈 수 있기에 굳이 중복문은 써주지 않는다

PYTHON CODE

def dfs(x, y, number):
    if len(number) == 6: #6자리 숫자가 만들어졌다면
        if number not in result: #result에 없다면
            result.append(number)
        return
        
    dx = [1, -1, 0, 0] #상하좌우 확인 x
    dy = [0, 0, 1, -1] #상하좌우 확인 y
    for k in range(4):
        ddx = x + dx[k]
        ddy = y + dy[k]
        
        if 0 <= ddx < 5 and 0 <= ddy < 5: #범위 내에 있다면
            dfs(ddx, ddy, number + matrix[ddx][ddy]) #6글자가 될 때 까지 재귀

#입력
matrix = [list(map(str, input().split())) for _ in range(5)]

result = []
for i in range(5):
    for j in range(5):
        dfs(i, j, matrix[i][j]) #0,0부터 4,4까지 모두 검사
print(len(result))