Daily LeetCode Challenge - 79. Word Search

Problem From.

https://leetcode.com/problems/word-search/

오늘 문제는 주어진 배열에서 상하좌우로 연속되는 블럭들을 연결하여 주어진 단어를 만들어 낼 수 있으면 true 아니면 false 를 반환하는 문제였다.

먼저 주어진 단어의 첫번째 낱말로 배열에서 시작점을 선택하고,
거기서부터 상하좌우로 옮겨가면서 다음 낱말이 있는지 검사하고 있으면 쭉쭉 탐색해 나가는 식으로 풀었다.

이를 위한 알고리즘은 dfs 로 구현하였다.

class Solution {
    
    fun exist(board: Array<CharArray>, word: String): Boolean {
        
        for(x in board.indices) {
            for(y in board[x].indices) {
                if(board[x][y] == word[0] && dfs(board, word, x, y, 0)) return true
            }
        }
        return false
    }
    
    private fun dfs(board : Array<CharArray>, word : String, x : Int, y : Int, match : Int) : Boolean {
        
        if(match == word.lastIndex) return true
        
        board[x][y] = '.'
        
        return when {
            isSafe(board, word[match + 1], x + 1, y) && dfs(board, word, x + 1, y, match + 1) -> true
            isSafe(board, word[match + 1], x - 1, y) && dfs(board, word, x - 1, y, match + 1) -> true
            isSafe(board, word[match + 1], x, y + 1) && dfs(board, word, x, y + 1, match + 1) -> true
            isSafe(board, word[match + 1], x, y - 1) && dfs(board, word, x, y - 1, match + 1) -> true
            else -> {
                board[x][y] = word[match]
                false
            }
        }  
    }
    
    private fun isSafe(board : Array<CharArray>, char : Char, x : Int, y : Int) =
        x in board.indices && y in board[x].indices && board[x][y] == char
    
}

처음에는 여느 dfs 문제와 같이 visit 배열을 만들어서 풀다가 공간복잡도를 줄이기위해 배열을 추가로 생성하지 않고 푸는 방식으로 바꾸었다.