[백준] 2780번: 비밀번호 문제 풀이 파이썬

문제

석원이는 자신의 현관문에 비밀번호 기계를 설치했다. 그 기계의 모양은 다음과 같다.

지나가던 석원이 친구 주희는 단순한 호기심에 저 비밀번호를 풀고 싶어한다. 이때 주희는 바닥에 떨어져 있는 힌트 종이를 줍게 된다. 이 종이에는 석원이가 비밀번호를 만들 때 사용했던 조건이 적혀 있다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다. 석원이의 힌트 종이는 다음과 같다.

비밀번호의 길이는 N이다.
비밀번호는 위 그림에 나온 번호들을 눌러서 만든다.
비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다.
(ex. 15 라는 비밀번호는 불가능하다. (1과 5는 인접하지 않는다. ) 하지만 1236이라는 비밀번호는 가능하다.)

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 비밀번호의 길이 N이 주어진다.( 1 <= N <= 1,000 )

출력

각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라.

첫번째 접근: DFS

문제를 읽자마자 처음으로 떠오른 것은 DFS 알고리즘이었다.
위의 이미지와 동일하게 2차원 배열을 만들고, 각 번호마다 length=1을 가지고 시작하여 주변번호로 이동할 때마다 length+=1, 그리고 length가 N이 되면 탐색을 멈추는 방식으로 가능한 비밀번호의 갯수를 셌다.

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

password = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [0, '*', '*']]

def dfs(a, b):
    queue = deque([[a, b, 1]])
    cnt = 0
    while queue:
        x, y, l = queue.pop()
        if l < N:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < 4 and 0 <= ny < 3 and password[nx][ny] != '*':
                    queue.append([nx, ny, l+1])
        else:
            cnt += 1
            print(x, y, l)
    return cnt

문제는 큰 수를 입력받게 되면 연산시간이 매우 커짐에 따라 시간초과 이슈가 발생한다는 것이었다.

두번째 접근: DP

각 시작 번호 별 비밀번호의 갯수를 배열에 저장해주었다.
비밀번호의 길이가 1씩 늘어날 수록 규칙을 찾을 수 있었다.
예를들어, 1에서 시작하는 길이가 2인 비밀번호의 갯수는 2에서 시작하는 길이가 1인 비밀번호 + 4에서 시작하는 길이가 1인 비밀번호의 갯수이다.
그리고, 1에서 시작하는 길이가 3인 비밀번호의 갯수는 2에서 시작하는 길이가 2인 비밀번호 + 4에서 시작하는 길이가 2인 비밀번호의 갯수가 된다.
점화식을 세우면 다음과 같다.

점화식
cur_password[1] = pre_password[2] + pre_password[4]
cur_password[2] = pre_password[1] + pre_password[3] + pre_password[5]

우선 탐색으로 풀면서 애먹던 문제가 DP로 접근하니까 생각보다 쉽게 정답을 도출할 수 있어서 조금은 어이가 없었다.

전체 코드

from sys import stdin
input = stdin.readline

T = int(input())
for _ in range(T):
    password = [1]*10
    N = int(input())
    for i in range(1, N):
        newPass = password.copy()
        # 길이가 N인 비밀번호의 갯수는 인접한 숫자의 길이가 N-1인 비밀번호의 갯수와 같다.
        password[0] = newPass[7]
        password[1] = newPass[2] + newPass[4]
        password[2] = newPass[1] + newPass[3] + newPass[5]
        password[3] = newPass[2] + newPass[6]
        password[4] = newPass[1] + newPass[5] + newPass[7]
        password[5] = newPass[2] + newPass[4] + newPass[6] + newPass[8]
        password[6] = newPass[3] + newPass[5] + newPass[9]
        password[7] = newPass[4] + newPass[8] + newPass[0]
        password[8] = newPass[5] + newPass[7] + newPass[9]
        password[9] = newPass[6] + newPass[8]
        
    print(sum(password)%1234567)

너무 우선 탐색으로만 풀려는 경향이 있었던 것 같다. 여러 알고리즘에도 익숙해져야 겠다는 생각이 들었다.