문제
석원이는 자신의 현관문에 비밀번호 기계를 설치했다. 그 기계의 모양은 다음과 같다.
지나가던 석원이 친구 주희는 단순한 호기심에 저 비밀번호를 풀고 싶어한다. 이때 주희는 바닥에 떨어져 있는 힌트 종이를 줍게 된다. 이 종이에는 석원이가 비밀번호를 만들 때 사용했던 조건이 적혀 있다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다. 석원이의 힌트 종이는 다음과 같다.
비밀번호의 길이는 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)
너무 우선 탐색으로만 풀려는 경향이 있었던 것 같다. 여러 알고리즘에도 익숙해져야 겠다는 생각이 들었다.
