[LeetCode] 79. Word Search - Java

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

Word Search - LeetCode

---

문제

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.

 

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

 

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

---

풀이

풀이 과정

m x n 사이즈의 2차원 배열이 주어지고 각 셀에는 알파벳이 들어있다. 찾아야하는 단어 word가 주어질 때 word가 이어진 셀로 존재한다면 true를 return한다.
이 때 동일한 셀은 중복해서 사용할 수 없다.

dfs를 사용하여 풀이한다.

우선 탐색에 사용할 함수를 생성한다.
탐색에 사용할 파라미터는 문자를 탐색할 대상 배열, 찾을 대상 단어, 단어 중 현재 탐색할 알파벳의 인덱스, 배열의 x좌표, 배열의 y좌표로 구성한다.
탐색 결과에 따라 true 혹은 false를 반환하도록 한다

/**
 * @param board         : 문자를 탐색할 대상 배열
 * @param word          : 찾을 대상 단어
 * @param wordIndex     : 현재 탐색중인 단어의 인덱스
 * @param x             : 배열의 x좌표
 * @param y             : 배열의 y좌표
 * @return
 */
public boolean wordSearch(char[][] board, String word, int wordIndex, int x, int y) {

}

 

함수 내에서는 아래의 조건들을 판단한다.

1. 현재 탐색중인 단어의 인덱스가 찾을 대상 단어의 인덱스와 같다면, 즉 단어의 길이만큼 탐색한 경우 word의 모든 알파벳을 비교한 것이므로 글자가 존재한다고 볼 수 있다. 따라서 true를 return 한다.

boolean result = false;
// 단어의 길이만큼 탐색했다면 글자가 존재하므로 true를 return
if(wordIndex == word.length()) return true;

 

2. x,y의 좌표가 배열을 벗어난다면 탐색이 불가능하므로 false를 return한다.

// 좌표가 배열을 벗어난다면 false를 return
if(x < 0 || y < 0 || x >= board.length || y >= board[0].length) return false;

 

3. 이미 방문한 좌표를 재방문하는 경우 중복된 셀을 사용할 수 없으므로 false를 return한다.
이때 방문한 좌표의 값은 '*'로 변경하여 판단하기로 한다. 

// 이미 방문했다면 false를 return
if(board[x][y] == '*') return false;

 

4. 현재 좌표값과 탐색 중인 문자가 일치하지 않는 경우 더 이상 탐색이 불필요하므로 false를 return한다.

// 문자가 일치하지 않는 경우 false를 return
if(board[x][y] != word.charAt(wordIndex)) return false;

 

5. 이외의 경우는 현재 좌표의 값과 탐색 중인 문자가 일치하는 경우이다.
이 경우에는 현재 좌표 값을 방문의 의미로 '*'로 세팅하고 상, 하, 좌, 우에 대해 단어 인덱스를 증가시켜 재탐색한다.
상하좌우를 탐색하기 위해 x,y좌표에 대한 이동 방향을 전역변수로 세팅하여 사용한다.
상하좌우에 대해 탐색한 결과값이 true가 나오는 경우 탐색을 중단한다. 해당 좌표에서 탐색이 종료되면 방문 표시 해두었던 '*' 값을 다시 원래의 값으로 되돌리고 결과값을 return한다.

class Solution {
    // 좌표의 이동 방향 ( 상, 하, 좌, 우 )
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    
    ...
    
    // 방문 표시
    board[x][y] = '*';
    // 상하좌우 탐색
    for(int i = 0; i < 4; i++) {
        result = wordSearch(board, word, wordIndex + 1, x + dx[i], y + dy[i]);
        if(result) break;
    }
    // 방문 표시 해제
    board[x][y] = word.charAt(wordIndex);
    
    // 결과값 return
    return result;

 

생성한 함수를 이용하여 배열의 모든 요소에 대해서 탐색한다.
탐색 중 true값이 return되는 경우 탐색을 중지하고 true를 최종 결과로 return한다.

public boolean exist(char[][] board, String word) {
    boolean result = false;
    int m = board.length;
    int n = board[0].length;

    // 배열의 요소 탐색
    for(int i = 0; i < m; i ++) {
        for(int j = 0; j < n; j++) {
            // 찾고자 하는 단어가 존재하는 경우 true를 return
            if(wordSearch(board, word, 0, i, j)) return true;
        }
    }

    return result;
}

---

최종 코드

class Solution {
    // 좌표의 이동 방향 ( 상, 하, 좌, 우 )
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    public boolean exist(char[][] board, String word) {
        boolean result = false;
        int m = board.length;
        int n = board[0].length;
        
        // 배열의 요소 탐색
        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j++) {
                // 찾고자 하는 단어가 존재하는 경우 true를 return
                if(wordSearch(board, word, 0, i, j)) return true;
            }
        }

        return result;
    }

    /**
     * @param board         : 문자를 탐색할 대상 배열
     * @param word          : 찾을 대상 단어
     * @param wordIndex     : 현재 탐색중인 단어의 인덱스
     * @param x             : 배열의 x좌표
     * @param y             : 배열의 y좌표
     * @return
     */
    public boolean wordSearch(char[][] board, String word, int wordIndex, int x, int y) {
        boolean result = false;
        // 단어의 길이만큼 탐색했다면 글자가 존재하므로 true를 return
        if(wordIndex == word.length()) return true;
        // 좌표가 배열을 벗어난다면 false를 return
        if(x < 0 || y < 0 || x >= board.length || y >= board[0].length) return false;
        // 이미 방문했다면 false를 return
        if(board[x][y] == '*') return false;
        // 문자가 일치하지 않는 경우 false를 return
        if(board[x][y] != word.charAt(wordIndex)) return false;
        
        // 방문 표시
        board[x][y] = '*';
        // 상하좌우 탐색
        for(int i = 0; i < 4; i++) {
            result = wordSearch(board, word, wordIndex + 1, x + dx[i], y + dy[i]);
            if(result) break;
        }
        // 방문 표시 해제
        board[x][y] = word.charAt(wordIndex);
        
        // 결과값 return
        return result;
    }
}

---