[백준] 2210번 숫자판 점프

💡문제접근

• 재귀를 이용하여 숫자판을 지나다니면서 만들어지는 숫자의 길이가 6자리가 되면 리스트에 해당 숫자가 있는지를 확인한 후에 없으면 추가하고 있으면 넣지 않는 방식을 이용했다. 또한 이 문제는 왔던 곳을 다시 지나갈 수 있으므로 방문 여부를 따지는 배열이 필요하지 않다.

💡코드(메모리 : 31256KB, 시간 : 644ms)

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

def DFS(x, y, number):
    number += graph[y][x]

    if len(number) == 6:
        if number not in result:
            result.append(number)
        return
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
            continue
        if 0 <= nx < 5 and 0 <= ny < 5:
            DFS(nx, ny, number)

graph = []
for i in range(5):
    graph.append(list(map(str, input().strip().split())))

result = []
for i in range(5):
    for j in range(5):
        k = DFS(i, j, '')
print(len(result))

💡소요시간 : 20m