[리트코드] 79. Word Search

79. Word Search

문제

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

 

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.

 

문제 분석

1. Input 분석

  • board → 문자들로 이루어진 m*n 크기의 grid

  • word → 찾아야 하는 문자열

 

2. output 분석

board의 현재 위치에서 수평과 수직 이동을 통해 word를 만들 수 있는지 검사

  • 있다면 true

  • 없다면 false

 

접근 방법

현재 위치에서 수평과 수직을 통해 grid 전체를 탐색해야하므로 완전 탐색으로 접근해 볼 수 있다. 이때 전부 다 판단해 볼 필요는 없고 가능성이 있는 부분만 탐색하면 되기에 재귀를 통한 백트래킹으로 풀 예정이다. word의 길이가 1 ~ 15 사이이고, m, n의 값도 1 ~ 6 사이로 범위가 적기 때문에 완전 탐색을 수행해도 시간 초과를 걱정하지 않아도 될 것 같다.

 

두 가지 방식

  • board와 같은 크기의 빈 visited 그리드를 생성하고, 처음에는 모든 값을 false로 초기화한다. 백트래킹을 시작하기 전에 해당 위치를 true로 설정하고, 다른 경우의 수를 검사하기 전에는 다시 false로 설정한다. → 선택

  • 새로운 배열을 만들지 않고, 기존 board에서 방문한 위치를 '.'로 바꾸고, 백트래킹이 끝난 후 원래 문자로 복원한다.

 

코드 구현

class Solution {
    public boolean exist(char[][] board, String word) {
        // board랑 같은 크기의 빈 visited grid 생성 -> 안에 false로 채우기
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 모든 위치에서 백트래킹 시작
                if (backtracking(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 동서남북 이동 방향 설정
    int[] dr = { 0, 0, 1, -1 };
    int[] dc = { 1, -1, 0, 0 };

    public boolean backtracking(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
        // 인덱스가 word의 길이와 같다면 모든 문자를 찾았다는 뜻이므로 true 반환
        if (index == word.length()) {
            return true;
        }

        // 범위를 벗어나거나 이미 방문했거나 현재 문자가 일치하지 않으면 false 반환
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }

        // 현재 위치 방문 처리
        visited[i][j] = true;

        // 동서남북으로 이동하여 백트래킹 시도
        for (int d = 0; d < 4; d++) {
            int newRow = i + dr[d];
            int newCol = j + dc[d];
            if (backtracking(board, word, visited, newRow, newCol, index + 1)) {
                return true;
            }
        }

        // 현재 위치 방문 해제
        visited[i][j] = false;

        return false;
    }
}

  • 실행 시간 (Runtime): 203ms

  • 메모리 사용량 (Memory): 41.33MB

 

회고

동서남북 이동 방향 설정에 대해 배웠다. grid를 수평과 수직으로 이동할 때 유용하게 쓰일 예정이다.

  • dr : 행 방향

  • dc : 열 방향

int[] dr = { 0, 0, 1, -1 }; 
int[] dc = { 1, -1, 0, 0 };

 

연속으로 백트래킹 문제를 풀다 보니 어느 정도 감이 잡히는 것 같아 다행이다. 😀