🔴 문제 개요
🚀 난이도 : GOLD 3
알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.
K A K T
X E A S
Y R W U
Z B Q P
이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다.
반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.
이와 같은 문자판과 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자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.
🟠 Solution
1️⃣ DFS 만을 활용한 풀이(시간 초과)
단순히 문제만을 이해하기로는 그래프 탐색 문제로, DFS를 활용해 재귀를 거듭하며 모든 경우의 수를 찾아내면 될 듯 합니다. 다만, 최대 K칸 까지 이동할 수 있다는 점과, 같은 지점을 다시 방문할 수 있다는 점을 고려하여 코드를 작성해야 합니다. 그러면 아래와 같이 기본적인 DFS 풀이의 구조로 코드를 완성할 수 있습니다.
import sys
input = sys.stdin.readline
N, M, K = map(int, input().rstrip().split())
matrix = [input().rstrip() for _ in range(N)]
st = input().rstrip()
# 상, 하, 좌, 우 탐색을 위함
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
# 경우의 수를 담을 global 변수
count = 0
def dfs(idx, y, x):
global count
# 글자가 완성되는 경우 카운트 추가
if idx == len(st) - 1:
count += 1
return
# 다음 칸 탐색, 상하좌우 최대 k칸
for k in range(1, K + 1):
for d in range(4):
ny = y + k * dy[d]
nx = x + k * dx[d]
# 다음 문자가 일치하는 경우만 재귀
if 0 <= ny < N and 0 <= nx < M and matrix[ny][nx] == st[idx + 1]:
dfs(idx + 1, ny, nx)
# 시작 좌표는 임의의 칸
for r in range(N):
for c in range(M):
if matrix[r][c] == st[0]:
dfs(0, r, c)
print(count)
하지만 이 경우 시간초과가 발생하게 됩니다. 제한 사항에 기재되어있는 대로 나올 수 있는 수의 범위를 최대로 고려하여 연산 횟수를 생각해보면 그 이유를 알 수 있습니다.
한 칸에서 이동 가능한 다른 칸은 최대 4방향 5칸이므로 20칸입니다. 그리고 단어의 길이는 최대 80이므로 80번 재귀한다 했을 때, 20^80의 어마무시한 연산량이 추정되겠네요. N, M이 100까지여도 이런 방식으로는 절대 시간 내에 통과가 어려울 것 같습니다.
2️⃣ DFS+DP를 활용한 풀이
여기서 DP 방법론을 활용할 수 있습니다. 단순 DFS만으로는 중복되는 재귀를 매우 많이 수행합니다.
예를 들어서 (4, 2) -> (3, 2) -> (2, 2) -> (1, 2) -> (1, 1)로 이어지는 경우의 수를 먼저 구하고, 다른 경우애 (3, 2) -> (3, 1) -> (2, 2) 로 이동하는 과정에서 3번째로 방문한 (2, 2)에 대해 이후의 경우의 수를 위해서 다시 재귀를 거친다면 동일한 재귀가 반복되게 됩니다. 그렇다면 첫 번째 재귀에서 이를 위해 별도의 memoization을 해준다면 이후 같은 상황에서 다시 재귀를 거치지 않고, 이를 참조만 해서 답을 구해낼 수 있을 것입니다.
위의 DFS 구조에서 memoization 과정만을 추가해보겠습니다.
import sys
input = sys.stdin.readline
N, M, K = map(int, input().rstrip().split())
matrix = [input().rstrip() for _ in range(N)]
st = input().rstrip()
# dp[y][x][idx] : (y, x)에 idx번 째로 방문했을 때 만들어지는 경우의 수 memoization
dp_matrix = [[[-1 for _ in range(len(st))] for _ in range(M)] for _ in range(N)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
count = 0
def dfs(idx, y, x):
# memoization 되어있는 경우 바로 결과 반환
if dp_matrix[y][x][idx] != -1:
return dp_matrix[y][x][idx]
# 글자가 완성되는 경우 카운트 추가
if idx == len(st) - 1:
return 1
# 새로운 memoization을 위한 카운트 이를 기점으로 앞으로의 경우의 수 카운트
cnt = 0
# 상하좌우 최대 k칸
for k in range(1, K + 1):
for d in range(4):
ny = y + k * dy[d]
nx = x + k * dx[d]
# 다음 문자가 일치하는 경우만 재귀
if 0 <= ny < N and 0 <= nx < M and matrix[ny][nx] == st[idx + 1]:
cnt += dfs(idx + 1, ny, nx)
# 경우의 수 memoization 업데이트
dp_matrix[y][x][idx] = cnt
return cnt
for r in range(N):
for c in range(M):
if matrix[r][c] == st[0]:
count += dfs(0, r, c)
print(count)우선 가장 크게, memoization을 위해 global 변수로 값을 저장하는 방식이 아닌, 함수에서 값을 반환하는 방식으로 변경하였습니다.
또한 현재 칸에서 재귀를 시작할 때 카운트(cnt)를 시작하여 재귀를 거쳐 경우의 수를 센 뒤, dp_matrix에 memoization 해주었습니다. 이를 함수의 시작 부분에서 참조해, 이미 기록되어있는 경우 즉시 해당 값을 반환할 수 있도록 변경하였습니다.
이렇게 그래프 탐색과 DP를 활용하는 방법은 제한 사항에서 수의 범위가 단순 DFS, BFS만으로는 버거울 때 꼭 활용해야 하는 방법인 것 같습니다. 이를 위해서 DFS를 수행할 때 함수에서 값을 반환하는 방법으로 코드를 작성하는 습관을 갖추기로 했습니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
0개의 댓글
