Leet code (Medium): 79. Word Search(DFS) - JAVA

 

 

DFS를 다시 한번 제대로 복습할 수 있었던 문제다.

문제의 핵심은 다음과 같다.

1. 주어진 목표 단어의 첫 알파벳과 일치하는 알파벳 칸을 발견하면 dfs 시작
2. 한번 사용된 알파벳 칸은 재사용 안됨. Ex) "abca" 일 때, 처음 'a'때 방문한 칸을 마지막 'a' 때 재방문 할 수 없음.
3. 따라서, 방문 체크 필요.
4. 방문 체크는 해당 dfs 뎁스에서만 유효함. (다른 칸에서 dfs로 탐색이 시작되면 모든 칸은 방문되지 않은 상태여야 함)
5. 따라서, 백트래킹 처리 필요

 

[방문 체크]

처음엔 방문 체크를 Set 객체를 사용해서 했는데 시간이 좀 오래걸려서

주어진 그래프 객체 board[row][col]를 업데이트하며 체크했다.

그랬더니 확연히 빨라졌다.

시간복잡도는 O(1)로 같겠지만,

아무래도 Set은 추가적인 메모리를 요구하고,

Set에 넣는 과정이 문자열을 조합해서 넣는 작업이다보니 좀 더 시간이 걸린것으로 보인다.

 

 

 

[백트래킹 처리]

현재 뎁스에서만 방문체크가 유효해야하므로,

백트래킹으로 dfs 재귀에서 빠져나올때, 방문체크를 해지하는 과정이 필요하다.

따라서, 방문 처리를 기존값을 무의미한 '*'로 업데이트 하고 있었기 때문에,

기존 board[row][col]의 값을 따로 temp로 저장해두고, dfs 재귀 호출 과정을 거친 후,

이후에 오는 백트래킹 작업으로 temp의 값을 다시 board에 업데이트 하는 식으로 구현했다.

 

class Solution {
    private int rows;
    private int cols;
    private int[] dr = {-1, 0, 0, 1};  // 상, 좌, 우, 하
    private int[] dc = {0, 1, -1, 0};

    public boolean exist(char[][] board, String word) {
        rows = board.length;
        cols = board[0].length;
        char[] charArr = word.toCharArray();

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] == charArr[0]) {  // 첫 글자가 일치하면 DFS 시작
                    if (dfs(row, col, board, charArr, 0)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    public boolean dfs(int currR, int currC, char[][] board, char[] charArr, int idx) {
        // 재귀 종료 조건: 모든 문자를 찾은 경우
        // (== 모든 문자를 찾고 난 직후인 경우)
        if (idx == charArr.length) {
            return true;
        }

        // 경계 체크 및 문자 일치 여부 확인
        if (currR < 0 || currR >= rows || currC < 0 || currC >= cols || board[currR][currC] != charArr[idx]) {
            return false;
        }

        // 현재 위치 방문 처리 (방문 여부를 보드 자체로 처리)
        char temp = board[currR][currC];  // 백트래킹을 위한 임시 저장
        board[currR][currC] = '*';  // 방문 처리

        // 사방 탐색
        for (int i = 0; i < 4; i++) {
            int nextR = currR + dr[i];
            int nextC = currC + dc[i];
            if (dfs(nextR, nextC, board, charArr, idx + 1)) {
                return true;  // 경로가 유효하다면 true 반환
            }
        }

        // 백트래킹: 방문 해제 (이전 상태로 되돌림)
        board[currR][currC] = temp;

        return false;  // 모든 경로가 유효하지 않다면 false 반환
    }
}