[LeetCode] Word Search(글자 찾기) 개인 풀이

문제

m x n 크기의 board와 문자열 하나가 주어집니다. board에서 문자열을 얻어낼 수 있다면 true 그렇지 않다면 false를 리턴하세요. board 한칸에는 하나의 문자가 들어가며 문자열은 한문자에서 한칸씩 이동하여 만들어야합니다. 또한 중복으로 접근하는것은 불가능 합니다.

예제 보드판

예제 1
입력 word = "ABCCED"
출력: true

[0,0] -> [0,1] -> [0,2] -> [1,2] -> [2,2] -> [1,2]로 가능

예제 2
입력 word = "SEE"
출력: true

[1,3] -> [2,3] - [2,2]로 가능

예제 3
입력 word = "ABCB"
출력: false

제한 사항
m == board.length
n == board[i].length
1 <= m, n <= 6
1 <= word.length <= 15

개인 풀이

먼저 제한 사항을 보면 board의 최대 크기는 6 * 6, 글자의 크기는 15라는 것을 알 수 있습니다. 이말은 시간복잡도적으로 O(N^3)는 무리 없음을 알 수 있습니다. 그리고 DFS를 재귀함수로 구현한다고 했을 때 최대 깊이 36으로 stackoverflow가 일어날 일은 없다는 것을 알 수 있습니다.

이러한 제한사항을 봤을 때 저는 board 전체를 찾으며 word 첫번째 글자를 매칭하고 그 이후 DFS를 통해 전체 문자가 맞게 있는지 찾는 로직으로 풀면 되겠다고 생각했고 그렇게 문제에 접근하였습니다.

코드

public boolean exist(char[][] board, String word) {

    char[] chars = word.toCharArray();

    for (int y = 0; y < board.length; y++) {
        for (int x = 0; x < board[y].length; x++) { // 첫번째 글자 찾기위한 2중 for문
            boolean[][] checkBoard = new boolean[board.length][board[0].length];
            if (board[y][x] == chars[0] && search(board, checkBoard, chars, x, y, 1) == word.length()) { // 첫글자를 찾고 search가 리턴한 크가가 word의 크기와 같으면 board에 글자 있다고 판단.
                return true;
            }
        }
    }
    return false;
}

public int search(char[][] board, boolean[][] checkBoard, char[] chars, int x, int y, int count) {

    // System.out.println("x = " + x + ", y = " + y + ", count = " + count);

    checkBoard[y][x] = true; // 한번접근한 곳 다시 접근하지 못하게
    int tempCount = count;

    if (tempCount != chars.length && x + 1 < board[0].length && board[y][x + 1] == chars[count] && !checkBoard[y][x + 1]) { // word의 길이와 탐색한 길이를 비교하여 다르고 board에 갈곳이 있는지 판단하여 재귀
        tempCount = search(board, checkBoard, chars, x + 1, y, count + 1);
    }

    if (tempCount != chars.length && y + 1 < board.length && board[y + 1][x] == chars[count] && !checkBoard[y + 1][x]) {
        tempCount = search(board, checkBoard, chars, x, y + 1, count + 1);
    }

    if (tempCount != chars.length && x > 0 && board[y][x - 1] == chars[count] && !checkBoard[y][x - 1]) {
        tempCount = search(board, checkBoard, chars, x - 1, y, count + 1);
    }

    if (tempCount != chars.length && y > 0 && board[y - 1][x] == chars[count] && !checkBoard[y - 1][x]) {
        tempCount = search(board, checkBoard, chars, x, y - 1, count + 1);
    }

    checkBoard[y][x] = false; // 더이상 돌곳이 없으면 다시 풀어주는 역할 

    return tempCount;
}

마무리

오늘은 이렇게 LeetCode의 Word Search 문제를 풀어보는 시간을 가져보았습니다. 감사합니다.