[LeetCode] 79. Word Search (Java) - DFS, 백트래킹

✔️ 오늘의 리트코드 공부 기록 – Word Search (백트래킹 사고의 시작)

---

 

문제 요약 (Word Search)

2차원 보드(board)에서 단어(word)가 상하좌우 인접한 연속 칸을 따라 존재하는지 확인하는 문제

 

문제링크: https://leetcode.com/problems/word-search

---

 

문제를 바라보는 관점

• 문제의 핵심 조건: “연속된 경로 + 이미 방문한 칸 재사용 금지”
• 그러면 질문을 이렇게 바꿀 수 있다. 👉 “보드에서 특정 칸을 선택하면 다음 칸은 어디로 이동할까?”
• 답: 항상 상하좌우로 갈 수 있는 선택지 중 아직 방문하지 않은 칸

여기서 자연스럽게 떠오르는 접근:

1. 특정 칸에서 시작해서 단어의 다음 글자를 탐색
2. 막히면 이전 상태로 돌아가서 다른 경로 탐색
   • 이 때 이전에 방문했던 노드는 다시 되돌려야 다른 경로에서도 탐색할 수 있다.

→ 바로 백트래킹(Backtracking) 사고

---

💡 핵심 아이디어

• DFS(Depth-First Search) + 백트래킹
  1. 단어의 첫 글자를 보드에서 찾는다
  2. 찾은 칸에서 상하좌우로 다음 글자를 재귀 탐색
  3. 막히면 이전 상태로 되돌아가 다른 경로 탐색 → 이것이 바로 백트래킹

위 해결로도 충분히 시간 안에 해결 가능하지만 더 최적화를 한다면 아래처럼 할 수 있다.

• 불필요한 탐색을 줄이는 최적화 (심화버전)
  • 글자가 보드에 충분히 존재하지 않으면 DFS 시작 안 함
  • 시작점을 드문 글자부터 선택해 DFS 분기 최소화

---

 

코드 (Java) - 최적화 포함

class Solution {
    private int m, n;
    private char[][] board;
    private char[] w;
    private boolean[][] vis;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.w = word.toCharArray();
        this.m = board.length;
        this.n = board[0].length;
        this.vis = new boolean[m][n];

        // 최적화: 글자 빈도 체크
        int[] cntBoard = new int[58];
        int[] cntWord = new int[58];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) cntBoard[board[i][j] - 'A']++;
        }
        for (char c : w) if (cntBoard[c - 'A'] < ++cntWord[c - 'A']) return false;

        // 단어 시작점 선택 최적화 (드문 글자부터)
        if (cntBoard[w[0]-'A'] > cntBoard[w[w.length-1]-'A']) reverse(w);

        // DFS 탐색
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] == w[0] && dfs(i, j, 0)) return true;
        return false;
    }

    private boolean dfs(int r, int c, int idx) {
        if (idx == w.length) return true;
        if (r<0 || r>=m || c<0 || c>=n || vis[r][c] || board[r][c]!=w[idx]) return false;

        vis[r][c] = true;
        boolean found = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1)
                     || dfs(r, c+1, idx+1) || dfs(r, c-1, idx+1);
        vis[r][c] = false; // 백트래킹
        return found;
    }

    private void reverse(char[] a) {
        int l=0, r=a.length-1;
        while(l<r) {
            char t=a[l]; a[l]=a[r]; a[r]=t;
            l++; r--;
        }
    }
}

 

 

📈 Time / Space Complexity

• 시간: O(m·n·4^k), k = 단어 길이
• 공간: O(m·n) (방문 배열 + DFS 스택)

---

Trie 접근 

 

나는 처음에 Trie 자료구조도 생각이 나서 이 방법으로도 어떻게 해결할 수 있을지 생각해 보았다.

• 여러 단어를 동시에 탐색할 때 접두사 공유로 탐색 가지치기 가능
• 단어가 하나 끝나면 Trie 노드를 통해 불필요한 탐색 종료

※ 다만 이 문제처럼 단일 단어를 찾을 때는 큰 장점이 없고, 여러 단어를 동시에 탐색하거나 단어들이 접두사를 공유할 때 유용하다.

// Trie 노드 정의
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null; // 단어 끝이면 저장
}

class Solution {
    private int m, n;
    private char[][] board;
    private boolean[][] vis;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        m = board.length;
        n = board[0].length;
        vis = new boolean[m][n];

        TrieNode root = new TrieNode();
        insert(root, word); // 단일 단어 Trie 생성

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (dfs(i, j, root)) return true;
        return false;
    }

    private void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'A';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.word = word;
    }

    private boolean dfs(int r, int c, TrieNode node) {
        if (r < 0 || c < 0 || r >= m || c >= n) return false;
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'A'] == null) return false;

        node = node.children[ch - 'A'];
        if (node.word != null) return true;

        board[r][c] = '#'; // 방문 표시
        boolean found = dfs(r+1, c, node) || dfs(r-1, c, node)
                     || dfs(r, c+1, node) || dfs(r, c-1, node);
        board[r][c] = ch; // 백트래킹
        return found;
    }
}

 

---

 

📝 이번 문제에서 얻은 깨달음

 

• “연속된 경로를 따라가야 한다” → DFS
• “막히면 되돌아가 다른 경로 시도” → 백트래킹
• 불필요한 탐색 제거 → 글자 빈도 체크, 드문 글자부터 시작
• 여러 단어 탐색 → Trie 활용 → 접두사 공유로 탐색 효율 극대화

Word Search I은 단일 단어 DFS + 백트래킹으로 충분
Word Search II는 Trie + DFS가 핵심