문제 개요
4×4 크기의 문자 보드와 단어 목록이 주어졌을 때, 보드 위에서 인접한 문자들을 연결하여 만들 수 있는 단어의 최대 개수를 구하는 문제입니다. 이때 각 단어를 만들 때는 한 칸을 한 번만 사용할 수 있지만, 서로 다른 단어를 만들 때는 같은 칸을 다시 사용해도 됩니다.
이동 방향은 상하좌우뿐 아니라 대각선 방향도 허용됩니다.
예제 입력
예를 들어 아래와 같은 문자 보드가 있다고 가정해 봅시다.
| m | b | f | d |
| x | a | y | a |
| t | z | t | r |
| s | q | q | q |
단어 목록이 words = ["bat", "far", "mat"]일 때, 출력 결과는 3입니다. 각 단어는 다음 경로로 만들 수 있습니다.
mat: [0,1] → [1,1] → [2,0]
bat: [0,2] → [1,1] → [2,2]
far: [0,2] → [1,3] → [2,3]
풀이 접근 방법
이 문제는 트라이(Trie) 자료구조와 DFS(깊이 우선 탐색) 백트래킹을 조합하면 효율적으로 해결할 수 있습니다. 트라이를 사용하면 보드를 탐색하는 도중에 현재까지 만든 문자열이 어떤 단어의 접두사인지 빠르게 확인할 수 있어, 불필요한 탐색을 줄일 수 있습니다.
알고리즘 단계
N := 행렬 A의 행 개수, M := 열 개수로 설정합니다.
빈 맵으로 트라이(trie)를 생성합니다.
words의 각 단어에 대해 트라이에 삽입합니다. 단어의 끝에는 "*" 키를 True로 표시하여 단어 완성 지점을 나타냅니다.
정답 변수 ans := 0으로 초기화합니다.
dfs(x, y, d) 함수를 정의합니다.
d에 "*"가 있으면 해당 단어가 완성된 것이므로 d["*"]를 삭제하고 ans를 1 증가시킵니다. 삭제함으로써 같은 단어가 중복해서 세어지지 않습니다.
현재 칸의 문자를 temp에 저장하고, A[x][y]를 "#"로 바꿔 재방문을 방지합니다(백트래킹).
(x-1 ~ x+1) × (y-1 ~ y+1) 범위의 모든 인접 칸을 확인하고, 행렬 범위 안에 있으며 해당 칸의 문자가 d에 존재하면 dfs(i, j, d[A[i][j]])를 재귀 호출합니다.
탐색이 끝나면 A[x][y]를 원래 문자인 temp로 복원합니다.
메인 로직에서는 행렬의 모든 칸 (i, j)를 순회하며, A[i][j]가 트라이에 존재하면 dfs(i, j, trie[A[i][j]])를 호출합니다.
마지막으로 ans를 반환합니다.
Python 구현 예제
아래 구현을 통해 더 잘 이해해 봅시다.
class Solution: def solve(self, A, words): N = len(A) M = len(A[0]) trie = dict() for word in words: current = trie for c in word: if c in current: current = current[c] else: current[c] = dict() current = current[c] current["*"] = True ans = 0 def dfs(x, y, d): nonlocal ans if "*" in d: del d["*"] ans += 1 temp = A[x][y] A[x][y] = "#" for i in [x - 1, x, x + 1]: for j in [y - 1, y, y + 1]: if 0 <= i < N and 0 <= j < M and A[i][j] in d: dfs(i, j, d[A[i][j]]) A[x][y] = temp for i in range(N): for j in range(M): if A[i][j] in trie: dfs(i, j, trie[A[i][j]]) return ans ob = Solution() matrix = [ ["m", "b", "f", "d"], ["x", "a", "y", "a"], ["t", "z", "t", "r"], ["s", "q", "q", "q"] ] words = ["bat", "far", "mat"] print(ob.solve(matrix, words))
입력
[ ["m", "b", "f", "d"], ["x", "a", "y", "a"], ["t", "z", "t", "r"], ["s", "q", "q", "q"] ], ["bat", "far", "mat"]
출력
3
핵심 포인트 정리
트라이(Trie): 여러 단어를 한 번에 저장하고 접두사 기반으로 빠르게 탐색할 수 있는 트리 자료구조입니다.
백트래킹: 현재 칸을 임시로 "#"로 표시해 같은 단어 내에서 한 칸을 두 번 사용하지 않도록 하고, 탐색 후 원래 값으로 복원합니다.
중복 방지: 단어 완성 시 트라이에서 "*" 표시를 삭제하므로, 동일한 단어가 여러 번 발견되더라도 한 번만 카운트됩니다.
8방향 탐색: 상하좌우와 대각선을 포함한 모든 인접 칸을 확인하므로, 대각선 이동도 자연스럽게 처리됩니다.