참고
문제해설
NOTE
•
입력 값 ⇒ 문자 이중 배열, 단어 배열
•
출력 값 ⇒ 문자 이중 배열에서 단어 배열에 있는 값들을 출력
문제 로직고민
NOTE
•
4각형에서 문자를 찾는걸 보고 BFS방식이 먼저 생각났다.
◦
찾으려는 문자열의 시작값을 이중 for문을 통해 찾은뒤 BFS로 문자열을 탐색하는 방법이다.
•
Trie방식으로 접근해본다.
◦
Trie방식으로 접근하면 이중 for문을 돌면서 해당 문자열의 상하좌우를 자식노드로 담고 시작 문자의 Node를 root로한 TrieNode를 생성하면 된다.
•
둘 중 어떠한 방식이 더 좋은가?
◦
근본적으로 2방식 모두 Tree에 기반된 탐색이며 큰 차이는 존재하지 않을거라 생각한다.
◦
2개의 방식을 적절히 섞어서 문제를 풀이한다.
•
이중 Node 배열을 생성하고, 상하좌우 방향의 Node를 자식으로 삼는다
◦
이렇게하면 root Node만 설정하면 Trie자료구조가 생성된다.
◦
그런데 상하좌우에 중복되는 문자가 있을 수 있다.
◦
그렇기에 상하좌우 idx 0~3을 두고 자식 노드를 넣은다음 다시 탐색시키도록 했다.
◦
(풀이 포기 이후) 위의 방식이 아마 문제였던것 같다. 이로인해 크기가 커진경우 많은 시간을 먹기떄문에 시간복잡도가 초과되었으며 Trie장점도 살리지 못했다.
◦
또한 BFS가 아닌 DFS가 유리한 방식인게 문자열 탐색의 경우 연속적인 값이기 떄문에 DFS가 더 유리하다.
작성코드
NOTE
class Solution {
int[] dir_y = {-1,0,1,0};
int[] dir_x = {0,1,0,-1};
public List<String> findWords(char[][] board, String[] words) {
int m = board.length;
int n = board[0].length;
Node[][] nodeArray = new Node[m][n];
Map<Character, LinkedList<Node>> map = new HashMap();
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
nodeArray[i][j] = new Node(board[i][j]);
}
}
// board 문자열 전체를 Node화 시킨다.
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
for(int k=0; k<4; k++){
int my = i+dir_y[k];
int mx = j+dir_x[k];
if(my < 0 || my >= m || mx < 0 || mx >= n) continue;
nodeArray[i][j].children[k] = nodeArray[my][mx];
}
char c = board[i][j];
map.putIfAbsent(c, new LinkedList<>());
map.get(c).add(nodeArray[i][j]);
}
}
List<String> result = new ArrayList();
for(String s : words){
char start = s.charAt(0);
if(map.containsKey(start)){
LinkedList<Node> temp = map.get(start);
for(Node node : temp){
Trie trie = new Trie(node);
if(trie.search(node, s, 1)) {
result.add(s);
break;
}
}
}
}
return result;
}
}
class Trie{
Node root;
Trie(Node node){
root = node;
}
public boolean search(Node node, String words, int cur){
if(words.length() == cur) return true;
char c = words.charAt(cur);
for(int i=0; i< 4; i++){
if(node.children[i] == null || node.children[i].val != c) continue;
return search(node.children[i], words, cur+1);
}
return false;
}
}
class Node{
Node[] children;
char val;
boolean isLast;
Node(char c){
children = new Node[4];
this.val = c;
isLast = false;
}
}
Java
복사
초기 코드
•
Trie를 사용하려 했는데, 사실상 BFS가 되어버렸다.
•
이중 노드배열을 생성하고, 각 노드의 상하좌우 범위의 노드를 자식으로 넣어주었다.
•
시작 위치 탐색을 쉽게하기 위해, Map으로 시작지점을 저장해주었다.
•
현재 코드를 제출해본 결과 Node를 중복으로 방문할 수 있어 실패했다.
class Solution {
int[] dir_y = {-1,0,1,0};
int[] dir_x = {0,1,0,-1};
public List<String> findWords(char[][] board, String[] words) {
int m = board.length;
int n = board[0].length;
Node[][] nodeArray = new Node[m][n];
Map<Character, LinkedList<Node>> map = new HashMap();
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
nodeArray[i][j] = new Node(board[i][j]);
}
}
// board 문자열 전체를 Node화 시킨다.
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
for(int k=0; k<4; k++){
int my = i+dir_y[k];
int mx = j+dir_x[k];
if(my < 0 || my >= m || mx < 0 || mx >= n) continue;
nodeArray[i][j].children[k] = nodeArray[my][mx];
}
char c = board[i][j];
map.putIfAbsent(c, new LinkedList<>());
map.get(c).add(nodeArray[i][j]);
}
}
List<String> result = new ArrayList();
for(String s : words){
char start = s.charAt(0);
if(map.containsKey(start)){
LinkedList<Node> temp = map.get(start);
for(Node node : temp){
Trie trie = new Trie(node);
if(trie.search(node, s, 1, new HashSet())) {
result.add(s);
break;
}
}
}
}
return result;
}
}
class Trie{
Node root;
Trie(Node node){
root = node;
}
public boolean search(Node node, String words, int cur, Set<Node> visited){
if(visited.contains(node)) return false;
if(words.length() == cur) return true;
visited.add(node);
char c = words.charAt(cur);
for(int i=0; i< 4; i++){
if(node.children[i] == null || node.children[i].val != c) continue;
if(search(node.children[i], words, cur+1, new HashSet<>(visited))) return true;
}
return false;
}
}
class Node{
Node[] children;
char val;
boolean isLast;
Node(char c){
children = new Node[4];
this.val = c;
isLast = false;
}
}
Java
복사
2번째 코드 (시간초과)
•
중복검사까지 완료 했지만 시간 초과가 발생한다. 아무래도 접근방식부터 틀렸던것같다.
•
해당 문제는 풀이를 포기하고 정답코드를 분석하는 방향으로 진행하겠다.
class Solution {
class TrieNode {
// TrieNode의 자식들을 표현하는 맵
Map<Character, TrieNode> children = new HashMap<>();
// 만약 해당 TrieNode가 단어의 끝이라면, word에 해당 단어를 저장함. 아니라면 null.
String word = null;
public TrieNode() {}
}
char[][] _board = null;
ArrayList<String> _result = new ArrayList<String>();
public List<String> findWords(char[][] board, String[] words) {
// Step 1: Trie 구조를 만든다.
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (Character letter : word.toCharArray()) {
if (node.children.containsKey(letter)) {
node = node.children.get(letter);
} else {
TrieNode newNode = new TrieNode();
node.children.put(letter, newNode);
node = newNode;
}
}
node.word = word; // 단어의 마지막 글자의 노드에 단어 저장
}
this._board = board;
// Step 2: 보드의 모든 셀에서 백트래킹 시작
for (int row = 0; row < board.length; ++row) {
for (int col = 0; col < board[row].length; ++col) {
if (root.children.containsKey(board[row][col])) {
backtracking(row, col, root);
}
}
}
return this._result;
}
// 핵심로직!
private void backtracking(int row, int col, TrieNode parent) {
Character letter = this._board[row][col];
TrieNode currNode = parent.children.get(letter);
// 현재 위치의 노드가 단어의 끝인지 확인
if (currNode.word != null) {
this._result.add(currNode.word);
currNode.word = null; // 중복을 방지하기 위해 단어 제거
}
// 탐색 전 현재 글자 표시
// 이미 방문했다는 표시를 하기 위함
this._board[row][col] = '#';
// 시계 방향으로 이웃 셀 탐색: 위, 오른쪽, 아래, 왼쪽
int[] rowOffset = {-1, 0, 1, 0};
int[] colOffset = {0, 1, 0, -1};
for (int i = 0; i < 4; ++i) {
int newRow = row + rowOffset[i];
int newCol = col + colOffset[i];
// 범위 벗어나는 경우 생략
if (newRow < 0 || newRow >= this._board.length || newCol < 0
|| newCol >= this._board[0].length) continue;
// 만약 자식노드중에 값이 있다면 넣는다.
if (currNode.children.containsKey(this._board[newRow][newCol])) {
backtracking(newRow, newCol, currNode);
}
}
// 탐색 종료 후 원래 글자로 복원
this._board[row][col] = letter;
// 최적화: 잎 노드를 점진적으로 제거
if (currNode.children.isEmpty()) {
parent.children.remove(letter);
}
}
}
Java
복사
정답 코드(GPT)
•
Trie는 board를 이용해서 만드는것이 아닌 words를 통해 생성한다.
◦
단어 목록을 Trie로 만든다음, BFS를 통해 탐색이 되는지 안되는지를 판단해야 했던것 같다.
•
재방문을 방지하는 방법은 board를 복사한 이후, 방문한 글자를 #으로 변경한다.
◦
HashSet<Node>같은 무거운 방식이 아닌 가장 간결한 방법이다.