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

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

 

 

★ 시작하기전에

문자열을 활용하여 모든 경우의 수를 싹 확인하는 방법을 사용하면 되는건가?

시간 초과나 메모리 초과가 나지 않을까?

이런 생각을 했다. 그런데 아무리 생각해도 이렇게 하지 않고는 방법이 없었다. 그냥 6자리를 만들때까지 이리저리 왓다갓다 하는 모든 경우를 구한다음, python의 set함수를 쓰고 총 갯수를 구하는 방법으로 구현했다.

 

import sys
sys.setrecursionlimit(1000000)

input = sys.stdin.readline
board = [list(map(str, input().split())) for _ in range(5)]

ans = []

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

def dfs(a, b, word=''):
    word += board[a][b]
    # 6개 됫으니 ans에 넣어두기 모든 경우를.
    if len(word) == 6:
        ans.append(word)
        return
    for i in range(4):
        nextR = a + dr[i]
        nextC = b + dc[i]
        if 0<= nextR< 5 and 0<= nextC < 5:
            dfs(nextR, nextC, word)
        
for i in range(5):
    for j in range(5):
        dfs(i, j)
print(len(set(ans)))

답일까? 아닐까? 했지만 답이다!

dfs 를 아니까 이런 유형은 어떻게 접근할지 알 것 같다. 당분간은 dfs만 파는걸로!!

dfs를 할때 함수 내에서 가지치기를 하여 조건에 제한을 주는 방법도 항상 생각하고 적용해보도록 하자.

※ return에 대한 생각을 하자. 함수를 통해 무슨 값을 얻고 싶으면 return을 무조건 지정해줘야한다.

(없으면, 그냥 보이지 않는 작동만 하게 된다!!)