[BOJ] 2186 문자판 (Python3)

문제

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.

K	A	K	T
X	E	A	S
Y	R	W	U
Z	B	Q	P

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 ‘X’ 표시된 곳으로 이동할 수 있다.

		X
		X
X	X		X	X
		X
		X

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

입력

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 231-1보다 작거나 같다.

정답 코드

from collections import deque

n, m, k = map(int, input().split())

graph = []

for i in range(n):
    graph.append(list(input()))
 
target = input()    

starts = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == target[0]:
            starts.append((i, j, 0))
dx = []
dy = []

for i in range(1, k + 1):
    dx.append(i)
    dx.append(-i)
    dx.append(0)
    dx.append(0)
    
for i in range(1, k + 1):
    dy.append(0)
    dy.append(0)
    dy.append(i)
    dy.append(-i)

answer = 0
dp = [[[-1 for i in range(len(target))] for _ in range(m)] for _ in range(n)]

def dfs(x, y, index):
    global answer
    
    if index == len(target) - 1:
        return 1 
    
    if dp[x][y][index] != -1:
        return dp[x][y][index]
    
    dp[x][y][index] = 0
    
    for i in range(k * 4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == target[index + 1]:
                dp[x][y][index] += dfs(nx, ny, index + 1)
                
    return dp[x][y][index]
    
answer = 0

for sx, sy, index in starts:
    answer += dfs(sx, sy, index)
    
print(answer)

문제 풀이

처음에는 보자마자 DFS로 풀어야하는 문제임을 알 수 있었다.

탐색을통해 k에따른 이동위치를 dx, dy로 설정해주 dfs를 사용하여 타겟문자를 따라가며 경우의 수를 세어주면 된다. 하지만 n과 m이 최대 100까지 가능하므로, 단순 dfs만 사용하면 1억번의 연산이 훌쩍 넘어 시간초과가 날 수 밖에 없다.

따라서 이러한 dfs문제에 시간초과가 발생했을때는 100이면 90 DP를 이용해 풀이해야하는데, 특히 메모제이션 방법으로 풀 수 있다.

DFS의 매개변수가 x, y, index 3개이므로 3차원 배열을 만들어 해당 dfs의 과정을 해당 3차원 배열에 기록해가며 이미 방문하여 기록했다면 해당 값을 리턴하는 방식으로 중복 방문하는 재귀의 개수를 줄이면 시간초과를 통과할 수 있다.