문제 개요
2차원 격자 형태의 보드(board)와 단어 목록(words)이 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 사전에 포함된 단어들 중에서 보드 위에서 실제로 만들 수 있는 모든 단어를 찾아내는 것입니다.
단어를 구성할 때는 반드시 다음 두 가지 규칙을 지켜야 합니다.
- 각 단어는 순차적으로 인접한 셀의 문자들을 연결하여 만들어야 하며, 인접 셀이란 상·하·좌·우로 붙어 있는 셀을 의미합니다.
- 같은 문자 셀은 하나의 단어 안에서 두 번 이상 재사용될 수 없습니다.
예를 들어 아래와 같은 입력이 주어진 경우를 생각해 볼 수 있습니다.
접근 방법: 트라이(Trie) + 백트래킹
이 문제는 트라이(Trie) 자료구조와 백트래킹(backtracking)을 결합하면 효율적으로 해결할 수 있습니다. 전체 풀이 과정은 다음과 같습니다.
- 검색 결과를 저장할 배열 result를 생성합니다.
- solve() 메서드를 정의합니다. 이 메서드는 board, d(현재 트라이 노드), i, j, s(현재까지 만든 문자열)를 매개변수로 받습니다.
- i 또는 j가 보드의 행·열 범위를 벗어나면 즉시 종료(false 반환)합니다.
- l := board[i][j] 로 현재 셀의 문자를 가져옵니다.
- l이 현재 트라이 노드 d에 존재한다면:
- d를 d[l]로 갱신하고, 문자열 s에 l을 이어붙입니다.
- d에 '#'(단어 끝 표시)가 있고 그 값이 유효하면 s를 result에 삽입한 뒤 d['#'] := 0으로 설정하여 중복 추가를 방지합니다.
- board[i][j] := '*' 로 바꿔 현재 셀을 방문 처리합니다.
- 아래(i+1), 오른쪽(j+1), 위(i-1), 왼쪽(j-1) 네 방향의 셀이 보드 범위 안에 있고 해당 문자가 d에 존재하면 solve()를 재귀적으로 호출합니다.
- 재귀 호출이 끝나면 board[i][j] := l 로 되돌려 원상 복구합니다(백트래킹).
- insert() 메서드를 정의합니다. 이 메서드는 word와 딕셔너리 t를 받아 트라이에 단어를 삽입합니다.
- current := t
- word의 각 문자 i에 대해: i가 current에 없으면 current[i] := 새로운 맵을 생성하고, current := current[i] 로 이동합니다.
- 탐색이 끝나면 current['#'] := 1 을 설정해 단어의 끝임을 표시합니다.
- 메인 메서드(findWords)에서는 다음 작업을 수행합니다.
- 맵 t를 생성하고, words의 모든 단어에 대해 insert(word, t)를 호출해 트라이를 구성합니다.
- 보드의 모든 셀 (i, j)에 대해 solve(board, t, i, j)를 호출합니다.
- result를 반환합니다.
구현 예제
아래 코드를 통해 동작 원리를 더 명확하게 이해할 수 있습니다.
class Solution(object):
def findWords(self, board, words):
self.result = []
t = {}
for word in words:
self.insert(word,t)
for i in range(len(board)):
for j in range(len(board[0])):
self.solve(board,t,i,j)
return self.result
def solve(self,board,d,i,j,s=""):
if i<0 or j<0 or i>=len(board) or j>=(len(board[0])):
return
l = board[i][j]
if l in d:
d = d[l]
s+=l
if "#" in d and d['#']:
self.result.append(s)
d['#'] = 0
board[i][j] = '*'
if i+1<len(board) and board[i+1][j] in d :
self.solve(board,d,i+1,j,s)
if j+1 < len(board[0]) and board[i][j+1] in d:
self.solve(board,d,i,j+1,s)
if i-1>=0 and board[i-1][j] in d :
self.solve(board,d,i-1,j,s)
if j-1>=0 and board[i][j-1] in d :
self.solve(board,d,i,j-1,s)
board[i][j] = l
def insert(self, word,t):
current = t
for i in word:
if i not in current:
current[i] = {}
current =current[i]
current['#']=1
ob = Solution()
print(ob.findWords([["o","a","a","n"],["e","t","e","a"],["i","h","k", "r"],["i","f","l","v"]],["oath","pea","tea","rain"]))입력
[["o","a","a","n"], ["e","t","e","a"], ["i","h","k","r"], ["i","f","l","v"]], ["oath","pea","tea","rain"]
출력
['oath', 'tea']
정리
이 풀이의 핵심은 모든 단어를 미리 트라이에 저장해 둔 뒤, 보드의 각 셀에서 출발하는 DFS 탐색 시 트라이와 일치하지 않는 경로를 조기에 차단하는 것입니다. 덕분에 무작정 모든 경로를 탐색하는 브루트포스 방식보다 훨씬 효율적이며, 이미 찾은 단어는 '#' 플래그를 0으로 바꿔 결과의 중복을 깔끔하게 제거할 수 있습니다.