[LeetCode] 79. Word Search

문제

 

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

 

→ m x n의 알파벳이 들어 있는 바둑판과 문자열이 주어진다, 만약 주어진 문자가 해당 바둑판에서 조합이 가능하다면 true를 리턴하라.

단어는 인접한 셀의 조합으로 만들어진다, 인접한 셀은 가로, 세로로 인접한 셀들을 말한다.

같은 문자의 셀은 한번밖에 사용되지 않는다.

 

 

 

 

내생각

 

문제를 보고 dfs로 풀면 되겠다! 하고 호기롭게 도전했지만 너무 오랜만에 알고리즘이라 그런지 쉽지 않았다. 알고리즘 잘하고 싶은데 ㅠ 성실함으로 밀고 나가야겠다.

 

그러니까 문제를 요약하자면 이렇다.

1. 주어진 문자가 해당 바둑판에서 조합이 가능하면 true, 가능하지 않으면 false 리턴하라.

2. 바둑판 조합을 인접한 위치로 이루어진다. (상하좌우)

3. 같은 문자의 위치를 중복 사용할 수는 없다.

 

주어진 좌표(Grid)에서 상하좌우로 이동하면서 첫번째 단어와 일치하는 위치를 찾는다. 그리고 해당 위치에서 dfs를 호출하여 상하좌우를 탐색하며 주어진 문자열이 존재하는지 확인하면 된다. 이 때 방문한 위치는 방문했다고 표시해야함. 그리고 위치 탐색이 끝나고 다음 문자로 넘어가면 방문처리 했던 건 다시 원상복구해야함!!

 

 

내 코드

 

class Solution {
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private boolean dfs(char[][] board, int y, int x, String word, int idx, boolean[][] visited){
        // 단어를 모두 찾았다면 true 반환
        if (idx == word.length()){
            return true;
        }

        // 방문 확인, 좌표 내 확인
        if (y < 0 || y >= board.length || x < 0 || x >= board[0].length || visited[y][x]){
            return false;
        }

        // 현재 위치의 문자가 단어와 일치하는지 확인
        if(board[y][x] == word.charAt(idx)){
            // 방문 처리
            visited[y][x] = true;
            // 상하좌우로 문자 찾기
            for (int[] d : dir){
                int newY = y + d[0];
                int newX = x + d[1];
                if (dfs(board, newY, newX, word, idx + 1, visited)) {
                    return true;
                }
            }
            // 방문 처리 초기화
            visited[y][x] = false;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        // 문자 그리드 탐색
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                // DFS
                if (dfs(board, i, j, word, 0, new boolean[board.length][board[0].length])){
                    return true;
                }
            }
        }
        return false;
    }
}