[PS] BOJ 2418 / 단어 격자
![[PS] BOJ 2418 / 단어 격자](/content/images/size/w2000/2025/09/-------------13.png)
문제 링크: https://www.acmicpc.net/problem/2418
DFS로 가능한 모든 경우의 수를 세는데, 메모이제이션을 활용해야 합니다.
풀이
1) DFS
단어 격자에서 주어진 단어를 읽는 방법의 개수를 찾기 위해서는 그래프 탐색을 활용해야 합니다. 단, 같은 단어를 중복해서 방문할 수 있으므로 방문 여부를 기록하지 않습니다.
격자 그래프에서 8방향 (상하좌우 + 대각선)으로 탐색할 수 있고, 찾고자 하는 단어를 순서대로 탐색해야 합니다. 따라서, 각 탐색 깊이에 맞는 글자가 있는 칸만 탐색을 계속할 수 있습니다.
DIFF = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
letters = [input().rstrip() for _ in range(H)]
word = input().rstrip()
cnt = 0
def dfs(r, c, depth):
if depth == L:
return 1
res = 0
for dr, dc in DIFF:
nr = r + dr
nc = c + dc
if 0 <= nr < H and 0 <= nc < W and letters[nr][nc] == word[depth]:
res += dfs(nr, nc, depth + 1)
return res
for r in range(H):
for c in range(W):
if letters[r][c] == word[0]:
cnt += dfs(r, c, 1)
print(cnt)DFS 구현
letters는 입력으로 받은 단어 격자,word는 단어 격자에서 찾고자 하는 단어입니다. 격자는 $H$의 높이와 $W$의 너비를 가지며,word의 길이는 $L$입니다.
2) 시간 초과 해결하기
위 코드로만 제출하면 시간 초과를 받습니다! 단어 격자의 최대 크기는 40,000이고, 찾고자 하는 단어의 최대 길이는 100자입니다. 같은 좌표를 중복해서 방문할 수 있으니, 각 깊이에서 모든 글자를 방문하는 최악의 경우를 가정할 시 40,000의 각 칸을 모두 탐색하는 과정을 100번이나 반복하게 되며 (40,000^100) 시간 초과가 일어납니다.
❓ $200 \times 200$의 단어 격자가 임의의 한 글자 x로 모두 채워져 있으며, 찾고자 하는 단어 또한 임의의 한 글자 $x$가 100번 반복되는 형태의 입력을 상상해 봅시다.
그렇다면, 어떻게 재귀 호출의 횟수를 줄일 수 있을까요? DFS에서 재귀 호출을 통해 답을 구하는 과정을 다시 생각해 봅시다.
현재 깊이 $D$ (단, $D < L$ 일 때) 단어 격자에서 $r$번 행의 $c$번 열에 위치한 칸을 탐색하고 있다고 가정해 봅시다. 이때 탐색 중인 단어의 글자는 word[D]이며, 다음에 탐색할 단어는 word[D+1]입니다. 이전에 다른 경로로 이 위치에 도달했더라도, 매 번 이 위치, 이 깊이에서 나머지 단어의 글자들을 찾는다면 언제나 같은 경로를 찾게 됩니다.
즉, dfs(r, w, depth)의 반환 결과는 이전에 어떤 경로로 도달했건 항상 같습니다. 그렇다면, dfs()의 호출 결과를 기록하고 한 번 계산한 경우는 다시 계산하지 않게 한다면 재귀 호출의 횟수를 획기적으로 줄일 수 있습니다. 이를 위해 DFS에 메모이제이션을 도입할 수 있습니다.
cnt = 0
memo = [[[-1 for _ in range(L)] for _ in range(W)] for _ in range(H)]
def dfs(r, c, depth):
print(f"DFS({r},{c}) depth={depth} // TILE = {letters[r][c]}")
if depth == L:
print(f"=> DEPTH = L")
return 1
if memo[r][c][depth] != -1:
print(f"=> memo: {memo[r][c][depth]}")
return memo[r][c][depth]
res = 0
for dr, dc in DIFF:
nr = r + dr
nc = c + dc
if 0 <= nr < H and 0 <= nc < W and letters[nr][nc] == word[depth]:
res += dfs(nr, nc, depth + 1)
memo[r][c][depth] = res
print(f"=> ({r},{c}) at {word[depth]} = {res}")
return res메모이제이션을 도입한 DFS
전체 코드
input = open(0).readline
H, W, L = map(int, input().split())
DIFF = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
letters = [input().rstrip() for _ in range(H)]
word = input().rstrip()
cnt = 0
memo = [[[-1 for _ in range(L)] for _ in range(W)] for _ in range(H)]
def dfs(r, c, depth):
print(f"DFS({r},{c}) depth={depth} // TILE = {letters[r][c]}")
if depth == L:
print(f"=> DEPTH = L")
return 1
if memo[r][c][depth] != -1:
print(f"=> memo: {memo[r][c][depth]}")
return memo[r][c][depth]
res = 0
for dr, dc in DIFF:
nr = r + dr
nc = c + dc
if 0 <= nr < H and 0 <= nc < W and letters[nr][nc] == word[depth]:
res += dfs(nr, nc, depth + 1)
memo[r][c][depth] = res
print(f"=> ({r},{c}) at {word[depth]} = {res}")
return res
for r in range(H):
for c in range(W):
if letters[r][c] == word[0]:
cnt += dfs(r, c, 1)
print(cnt)solution.py