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

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

2210번: 숫자판 점프

POINT

• 임의의 자리에서 상, 하, 좌, 우로 5번 이동하며 가능한 수의 개수를 구해야하기 때문에 DFS(Death-First Search)를 이용한다.
• 6자리의 000000 ~ 999999의 수가 만들어지므로 1000000자리의 visitied 배열을 사용한다.

graph=[]
for i in range(5):
    graph.append(list(map(int,input().split())))
    
visited = [False] * 1000000

# 기본적으로 좌표가 인수로 주어지고, 변형이 필요한 값을 추가로 넘긴다
def dfs(x, y, visited, move, index):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 5번 이동하면 방문 체크하고 종료
    if move == 5:
        visited[index] = True
        return
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < 5 and 0 <= ny < 5):
        	# 이동 횟수 증가, index에 숫자 더하기
            dfs(nx, ny, visited, move + 1, index * 10 + graph[nx][ny])
            
    return

for i in range(5):
    for j in range(5):
        dfs(i, j, visited, 0, graph[i][j])
        
answer = 0        
for v in visited:
    if v == True:
        answer += 1
        
print(answer)