[Python] 숫자판 점프 - 백준 (DFS)

해당 글은 백준 2210번 문제 '숫자판 점프'을 다룬다.

문제

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

2210번: 숫자판 점프

 

설명

해당 문제는 방문 체크를 하지 않은 DFS로 해결할 수 있다.

중복 방문 가능하므로 방문 체크를 하지 않고, 문자열의 길이가 6이 되면 result에 결과값을 담고 함수를 종료한다.

단, result 배열에는 중복되는 값들이 들어가 있을 수 있으므로 set 함수를 통해 중복을 제거하여 결과값을 출력해준다.

 

코드

arr = []
for _ in range(5):
    arr.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

result = []
def dfs(x, y, s):
    if len(s) == 6:
        result.append(s)
        return
    s += str(arr[x][y])
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < 5 and ny >= 0 and ny < 5:
            dfs(nx, ny, s)

for i in range(5):
    for j in range(5):
        dfs(i, j, '')
print(len(set(result)))