https://leetcode.com/problems/implement-trie-prefix-tree/description/ : 208. Implement Trie (Prefix Tree)
https://youtu.be/asbcE9mZz_U?si=7ovXqcPW-mJDtg7h
class TrieNode:
def __init__(self):
self.children = {} # 자식 노드를 저장하는 딕셔너리 (예: {'a': TrieNode()})
self.isWord = False # 현재 노드가 단어의 끝인지 여부를 나타내는 플래그
def addWord(self, word):
cur = self # 현재 노드에서 시작
for c in word:
if c not in cur.children: # 현재 문자가 자식 노드에 없으면
cur.children[c] = TrieNode() # 새 TrieNode 생성 후 추가
cur = cur.children[c] # 현재 노드를 자식 노드로 이동
cur.isWord = True # 단어 끝 노드에 isWord를 True로 설정
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode() # Trie의 루트 노드 생성
# 주어진 words를 Trie에 추가
for w in words:
root.addWord(w)
# 보드 정보 가져오기
ROWS, COLS = len(board), len(board[0]) # 보드의 행과 열 크기
res, visit = set(), set() # 결과를 저장할 집합과 방문한 셀 추적을 위한 집합 초기화
# DFS 탐색 함수 정의
def dfs(r, c, node, word):
# base case: 탐색을 종료할 조건
if (r < 0 or c < 0 or # 보드의 경계를 벗어난 경우
r == ROWS or c == COLS or # 보드의 끝을 초과한 경우
(r, c) in visit or # 이미 방문한 셀인 경우
board[r][c] not in node.children): # 현재 문자가 트라이에 없는 경우
return
# 현재 셀을 방문했다고 표시
visit.add((r, c))
# 현재 노드 갱신 및 단어에 문자 추가
node = node.children[board[r][c]] # 현재 문자의 자식 노드로 이동
word += board[r][c] # 현재 문자를 단어에 추가
if node.isWord: # 현재 노드가 단어의 끝이면
res.add(word) # 결과 집합에 단어 추가
# 4방향으로 DFS 탐색
dfs(r - 1, c, node, word) # 위쪽 셀 탐색
dfs(r + 1, c, node, word) # 아래쪽 셀 탐색
dfs(r, c - 1, node, word) # 왼쪽 셀 탐색
dfs(r, c + 1, node, word) # 오른쪽 셀 탐색
# 탐색이 끝난 후 방문 표시를 해제 (백트래킹)
visit.remove((r, c))
# 보드의 모든 셀에서 DFS 시작
for r in range(ROWS): # 보드의 각 행에 대해 반복
for c in range(COLS): # 각 열에 대해 반복
dfs(r, c, root, "") # DFS 호출, 초기 단어는 빈 문자열
return list(res) # 결과를 리스트로 변환하여 반환
한글 주석 설명
- TrieNode 클래스:
- Trie 자료구조의 각 노드를 정의하며, 자식 노드와 단어의 끝임을 나타내는 플래그를 가집니다.
- addWord 메서드는 트라이에 단어를 추가하는 역할을 합니다.
- Solution 클래스:
- findWords 메서드는 주어진 보드와 단어 리스트에서 존재하는 단어를 찾는 메인 함수입니다.
- dfs 함수는 재귀적으로 보드의 셀을 탐색하며 가능한 단어를 구성합니다.
- 탐색 종료 조건(base case)과 백트래킹을 통해 방문 상태를 관리합니다.
- 각 줄마다 세부적으로 설명해, 코드의 흐름과 로직이 명확하도록 주석을 추가했습니다.
GPT 풀이
트라이(Trie) 자료구조와 백트래킹(Backtracking)을 조합해서 효율적으로 풀 수 있습니다. 이 문제를 푸는 핵심은:
- Trie 자료구조: words 리스트를 효율적으로 탐색하기 위해 트라이를 사용합니다.
- 백트래킹: 보드의 각 위치에서 시작하여 가능한 단어를 탐색합니다.
- 중복 사용 방지: 같은 셀을 두 번 사용할 수 없도록 방문한 셀을 추적합니다.
아래는 단계별로 풀이하는 방법과 구현 코드입니다.
풀이 전략
- 트라이에 단어 삽입:
- words 리스트에 있는 모든 단어를 트라이에 삽입합니다.
- 각 노드는 현재까지의 접두사를 나타내며, 단어의 끝을 표시하는 플래그를 추가합니다.
- 보드에서 백트래킹:
- 보드의 각 셀에서 탐색을 시작합니다.
- 현재 셀의 문자가 트라이에 있는지 확인하고, 있다면 다음 방향으로 재귀적으로 탐색합니다.
- 이미 방문한 셀은 다시 탐색하지 않도록 추적합니다.
- 종료 조건:
- 현재 노드가 트라이의 단어 끝을 나타내는 경우 결과에 추가합니다.
- 유효하지 않은 경로는 탐색을 종료합니다.
class TrieNode:
def __init__(self):
self.children = {} # 자식 노드들
self.word = None # 노드에서 끝나는 단어 (있다면 저장)
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.word = word # 단어 끝에 단어 저장
class Solution:
def findWords(self, board, words):
# 1. Trie에 단어 삽입
trie = Trie()
for word in words:
trie.insert(word)
# 2. 결과를 저장할 집합 (중복 방지)
result = set()
rows, cols = len(board), len(board[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 우, 하, 좌, 상 방향
# 3. DFS 백트래킹 함수
def backtrack(r, c, node):
if board[r][c] not in node.children: # 현재 문자가 트라이에 없으면 종료
return
char = board[r][c]
next_node = node.children[char]
if next_node.word: # 현재 노드에서 끝나는 단어가 있으면 결과에 추가
result.add(next_node.word)
# 방문 처리
board[r][c] = "#" # 방문한 셀 표시
# 4방향 탐색
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
backtrack(nr, nc, next_node)
# 방문 처리 복구
board[r][c] = char
# 4. 보드의 모든 셀에서 탐색 시작
for r in range(rows):
for c in range(cols):
backtrack(r, c, trie.root)
return list(result)
# 사용 예시
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath", "pea", "eat", "rain"]
solution = Solution()
print(solution.findWords(board, words)) # Output: ["eat", "oath"]
코드 설명
- Trie 자료구조:
- Trie 클래스는 insert 메서드를 통해 단어를 삽입합니다.
- 각 단어의 마지막 문자 노드에 word 값을 저장해 단어의 끝을 표시합니다.
- DFS 백트래킹:
- 보드의 각 셀에서 시작하여 트라이에 저장된 단어를 찾습니다.
- 방문한 셀은 "#"로 표시해 재방문을 방지합니다.
- 탐색이 끝난 후 원래 문자를 복구합니다.
- 결과 저장:
- result는 집합(set)을 사용해 중복된 단어를 방지합니다.
- 탐색이 끝난 후 리스트로 반환합니다.
최종 코드
# TrieNode 클래스는 트라이의 각 노드를 정의함
class TrieNode:
def __init__(self):
self.children = {} # 자식 노드를 저장하는 딕셔너리 (문자 → TrieNode)
self.wordFinish = False # 단어가 이 노드에서 끝나는지를 나타내는 플래그
# Trie 클래스는 단어들을 저장할 접두사 트리 구조를 구성
class Trie:
def __init__(self):
self.root = TrieNode() # 루트 노드를 초기화
def insert(self, word):
curr = self.root # 루트부터 시작
for c in word:
# 현재 문자가 자식 노드에 없으면 새 노드 생성
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c] # 다음 노드로 이동
curr.wordFinish = True # 단어의 끝을 표시
# 단어 찾기 메인 함수 정의
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# 단어 삽입
trie = Trie()
for word in words:
trie.insert(word) # 주어진 단어들을 Trie에 삽입
# 결과 변수 생성
# res = [] 후 res.append(char) 해도 되지만,
# --> 중복으로 단어가 들어갈 수도 있어서
# --> set() 변수로 만듦
res = set() # 중복 단어 방지를 위해 set 사용
rows, cols = len(board), len(board[0]) # 보드 크기 저장
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 우, 하, 좌, 상 방향 정의
# 현재 경로로 구성된 문자열을 함께 전달
def backtrackDFS(r, c, node, path):
# 해당 node 에 board 문자가 없으면 종료
char = board[r][c]
if char not in node.children:
return
next_node = node.children[char] # 현재 문자에 해당하는 다음 Trie 노드
new_path = path + char # 현재 경로에 문자 추가
# 단어가 끝나면 경로 문자열을 결과에 추가
if next_node.wordFinish:
res.add(new_path) # set() 변수여서 중복 없이 저장됨
# 방문 표시
board[r][c] = "#" # 현재 셀을 방문 표시하여 중복 경로 방지
for dr, dc in directions:
nr, nc = r + dr, c + dc # 다음 위치 계산
# 다음 위치가 유효하고 방문하지 않았다면 DFS 재귀 호출
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
backtrackDFS(nr, nc, next_node, new_path)
# 방문 표시 해제(복구)
board[r][c] = char # DFS가 끝난 후 원래 문자로 되돌리기 (백트래킹)
# 보드의 모든 셀에서 DFS 시작
for r in range(rows):
for c in range(cols):
backtrackDFS(r, c, trie.root, "") # 경로는 빈 문자열로 시작
return list(res) # set 변수여서 list 변환하여 return
📌 덧붙여 설명
- Trie는 문자 단위로 연결된 트리 구조로, 접두사 탐색에 최적화되어 있어요.
- backtrackDFS는 보드를 하나씩 탐색하며, Trie를 따라가는 방식입니다.
- 단어 중복을 방지하기 위해 set()을 사용했고, 마지막에 list()로 변환해 반환합니다.
'LeetCode > NeetCode' 카테고리의 다른 글
| [Backtracking: Combinations]: 39. Combination Sum ★ (0) | 2024.12.27 |
|---|---|
| [Backtracking: Combinations] 77. Combinations (0) | 2024.12.26 |
| [Two Heaps] Heap-PrioiryQueue: 295. Find Median from Data Stream ★★★ (0) | 2024.12.22 |
| [Two Heap] 502. IPO ★★★★★ (0) | 2024.12.22 |
| BST: 74. Search a 2D Matrix ★★★ (1) | 2024.12.20 |