단어 검색 II: 트라이와 격자 백트래킹
모든 목표 단어를 트라이에 삽입하고 2차원 보드에서 DFS 백트래킹을 실행해 O(m × n × 4^L) 시간에 유효한 모든 단어를 동시에 찾습니다.
단어 검색 II: 트라이와 격자 백트래킹은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
단어 검색 II 문제
단어 검색 II(LeetCode 212)는 m × n 크기의 문자 보드와 단어 목록이 주어졌을 때, 가로 또는 세로로 인접한 셀을 차례로 사용하여 만들 수 있는 모든 단어를 찾는 문제입니다. 각 셀은 한 번만 사용할 수 있습니다. 하나의 단어만 찾는 단어 검색 I보다 어려운 이유는 모든 일치 단어를 동시에 찾아야 하기 때문입니다. 각 단어에 대해 단순히 단어 검색 I을 실행하는 방법은 O(W × m × n × 4^L)이라 너무 느립니다.
왜 트라이와 백트래킹을 함께 사용할까요
모든 대상 단어를 트라이에 삽입한 다음 보드에서 DFS 백트래킹을 실행하면 모든 단어를 동시에 search할 수 있습니다. 보드의 각 셀에서 현재 경로가 '내 대상 단어를 완성하는가?'를 확인하는 대신 '이 경로가 트라이의 접두사와 일치하는가?'를 확인합니다. 트라이 접두사와 일치하지 않는 순간 DFS 분기 전체를 가지치기하므로, 같은 접두사를 공유하는 모든 단어에 대해 중복 작업을 수행하지 않아도 됩니다.
단어 목록에서 트라이 구축하기
모든 단어를 트라이에 삽입합니다. 단순히 불리언 값만 저장하지 않고 리프 노드의 node.word에 완전한 단어를 저장하면, 백트래킹 중 완전한 일치가 발견되었을 때 문자를 하나씩 다시 조합하지 않고 즉시 결과에 단어를 추가할 수 있습니다.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')격자에서 DFS 백트래킹
보드의 모든 셀에서 DFS를 시작합니다. 각 단계에서는 다음을 수행합니다. (1) 현재 셀의 문자가 현재 트라이 노드의 자식으로 존재하는지 확인합니다. (2) 존재하면 셀을 방문한 것으로 표시하고(예: '#'와 같은 센티널로 설정), 4개의 이웃 셀로 재귀 호출합니다. (3) 재귀 호출이 끝나면 셀을 원래 값으로 복원합니다. 트라이 노드에 None이 아닌 word가 있으면 결과에 추가하고 중복을 방지하기 위해 None으로 설정합니다.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']복잡도 분석
시간 복잡도: L을 최대 단어 길이라고 할 때 O(m × n × 4^L)입니다. m×n개의 시작 셀 각각에 대해 DFS가 최대 4^L개의 경로를 탐색합니다. 트라이는 어떤 단어의 접두사와도 일치하지 않는 경로를 가지치기하므로 실제로는 훨씬 빠릅니다. 트라이 구축에는 W를 단어 수라고 할 때 O(W × L)이 걸립니다. 공간 복잡도는 트라이에 O(W × L), 재귀 호출 스택 깊이에 O(L)입니다.
가지치기: 단어를 찾은 후 리프 노드 제거
단어를 찾은 후 자식이 없다면 단어만 비우지 말고 트라이에서 리프 노드를 제거합니다. 그러면 이후 DFS 호출에서 이미 막힌 분기를 다시 방문하지 않게 됩니다. 단어를 찾은 뒤 어떤 노드의 자식이 비게 되면 부모의 자식 딕셔너리에서 해당 노드를 제거합니다. 이 최적화는 많은 단어가 긴 접두사를 공유할 때 특히 효과적입니다.
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')노드에 단어를 저장하는 편이 나은 이유
DFS 경로에서 완전한 단어를 다시 조합하는 대신 트라이의 리프 노드에 저장하면 두 가지 장점이 있습니다. (1) 일치 항목을 찾았을 때 경로를 O(L) 시간에 재구성하지 않고 O(1)에 단어를 가져올 수 있습니다. (2) 단어를 찾은 후 node.word = None으로 설정하면 별도의 결과 집합 없이도 O(1)에 중복을 제거할 수 있습니다. 특히 단어 검색 II에서는 같은 단어를 이론적으로 서로 다른 경로에서 찾을 수 있으므로 중복 방지가 중요합니다.
방문한 셀을 제자리에서 표시하기
각 DFS 경로마다 O(m × n)의 공간이 필요한 별도의 visited 집합을 사용하는 대신, 셀의 문자를 '#'와 같은 센티널로 바꾸어 제자리에서 표시합니다. DFS가 반환되면 원래 문자를 복원합니다. 이 기법은 (1) 셀마다 추가 공간을 O(1)만 사용하고, (2) 하나의 경로 안에서 셀을 다시 방문하는 것을 자동으로 방지하며, (3) '#'가 트라이에 절대 나타나지 않으므로 트라이 순회에 전혀 영향을 주지 않습니다.
처리해야 할 예외 상황
중요한 예외 상황은 다음과 같습니다. (1) 단어 목록에 중복 단어가 있는 경우 — 집합에 저장하거나 node.word = None 기법을 사용하여 결과 중복을 방지합니다. (2) 보드의 크기를 초과하는 매우 긴 단어 — 만들 수 없지만 DFS가 자연스럽게 인접 셀을 모두 소진하므로 처리됩니다. (3) 셀이 하나뿐인 보드 — 한 글자로 된 단어만 찾을 수 있습니다. (4) 서로 다른 경로로 같은 단어를 만들 수 있는 경우 — node.word = None 기법으로 이중 집계를 방지합니다.
단순한 접근법과의 비교
단순한 접근법에서는 W개의 각 단어에 대해 단어 검색 I을 실행하므로 O(W × m × n × 4^L)입니다. 트라이를 사용하면 W의 크기와 관계없이 모든 단어를 동시에 search하여 O(m × n × 4^L)에 해결할 수 있습니다. 길이가 10인 단어 1000개를 10×10 보드에서 찾는 경우, 단순한 방법은 트라이를 사용하는 방법보다 1000배 느립니다. 트라이는 모든 단어에 공유되는 접두사 필터로 작동하여 비용을 분산시키며, 자료 구조를 사용해 점근적 성능 향상을 얻는 대표적인 사례입니다.
전체 해결 방법 요약
단어 검색 II의 전체 해결 방법은 다음과 같습니다. 단어들을 사용해 트라이를 구축하고 리프에 단어 문자열을 저장합니다. 보드의 각 셀에서 DFS를 실행하여 현재 문자가 현재 트라이 노드에 존재하는지 확인하고, 셀을 '#'로 표시한 뒤 4개의 이웃 셀로 재귀 호출하고 셀을 복원합니다. node.word가 비어 있지 않으면 결과에 추가하고 없음으로 설정합니다. 사용 후 비어 있는 트라이 분기를 선택적으로 가지치기할 수 있습니다. 결과 목록을 반환합니다. 시간 복잡도: O(m×n×4^L), 공간 복잡도: 트라이에 O(W×L) + 재귀 호출에 O(L)입니다.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result빠른 확인
이 단원에서 배운 자료 구조 & 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.
단원 요약
이 단원에서는 단어 검색 II가 공유 접두사 가지치기를 활용하는 트라이로 여러 단어를 동시에 search한다는 점, 트라이 리프에 단어 문자열을 저장하면 O(1)에 단어를 가져올 수 있고, 찾은 후 없음으로 설정하여 쉽게 중복을 제거할 수 있다는 점, 그리고 '#'로 방문 여부를 제자리에서 표시하면 각 DFS 경로마다 O(m×n)의 추가 공간을 사용하지 않아도 된다는 점을 배웠습니다. 이것으로 트라이와 문자열 알고리즘 과정을 마칩니다. 면접에서 사용되는 가장 강력한 문자열 특화 자료 구조 중 하나를 익혔습니다.
자주 묻는 질문
“단어 검색 II: 트라이와 격자 백트래킹” 강의는 무료인가요?
네 — “단어 검색 II: 트라이와 격자 백트래킹” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“단어 검색 II: 트라이와 격자 백트래킹”에서 뭘 배우나요?
모든 목표 단어를 트라이에 삽입하고 2차원 보드에서 DFS 백트래킹을 실행해 O(m × n × 4^L) 시간에 유효한 모든 단어를 동시에 찾습니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“단어 검색 II: 트라이와 격자 백트래킹” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- TrieNode 클래스: 삽입과 검색
- 접두사 검색과 Starts-With
- 트라이에서 와일드카드와 정규식 검색
- 단어 검색 II: 트라이와 격자 백트래킹