[LeetCode] word search

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

 

 

<<2트>>

접근 방법

-dfs(backtrack)을 이용한 풀이

• dfs함수의 리턴값을 boolean으로 주어 방향마다 전진 가능한지 여부 체크

-해당 노드가 유효하려면, 전진이 가능한지 여부도 체크해야함.

-isValid() 조건 1) 범위 벗어나면X 2) 방문했으면X 3) charAt(idx)와 같아야함

-재귀적으로 dfs 메서드 호출하고 하나라도 true를 반환하면 전체 탐색을 멈추고 true를 반환한다. 리턴되지 못하고 빠져나오면 false라는 의미이므로 방문 취소하고 다른 경우의 수 탐색

-최종 리턴값이 boolean타입이기 때문에 dfs도 boolean타입인 게 헷갈리지 않음

코드 구현

class Solution {
    public boolean exist(char[][] board, String word) {
        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(dfs(visited,board,word,0,i,j)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(boolean[][] visited,char[][] board, String word,int idx,int x,int y){
        if(idx==word.length()) return true;
        if(!isValid(board,word,x,y,idx,visited)) return false;
        visited[x][y]=true;
        
        int[] toX={-1,1,0,0};
        int[] toY={0,0,-1,1};
        for(int i=0;i<4;i++){
            if(dfs(visited,board,word,idx+1,x+toX[i],y+toY[i])){
                return true;
            }
        }
        
        visited[x][y]=false;
        return false;
    }
    public boolean isValid(char[][] board, String word,int x,int y,int idx,boolean[][] visited){
        return x>=0 && x<board.length && y>=0 && y<board[0].length && board[x][y]==word.charAt(idx) &&!visited[x][y];
    }
}

 

 

<<1트>>

문제 파악

-순열 문제로, 방문 여부를 확인한다.

-보드의 각 셀에서 시작하여 문자열을 탐색

• 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.

접근 방법

💡 -기존의 순열 구하듯이 구하면 안되고, 이 문제가 순열인 이유는 주어진 보드의 크기가 정해지고 이를 순회하는 것이기 때문에 원소 중심이 아니라, 위치 중심으로 방문을 판별해야 하기 때문.

-문자열의 다음 문자를 찾기 위해 재귀적으로 호출하며, 문자열이 보드에서 발견되면 탐색을 중단

-2차원 배열로 주어지는 값을 2중 for문을 돌며 컬럼값과 로우값을 부여하고, 최초의 backtrack을 불러온다.

-모든 재귀 순회가 끝나고 첫 재귀함수로 돌아오면, 돌려받은 값이 true인지, false인지에 따라 값을 리턴

-목표 문자열의 마지막 문자까지 도달하면 종료

 

코드 구현

import java.util.*;
public class Solution {
    boolean answer = false;

    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        boolean[][] visited = new boolean[board.length][board[0].length];

        for (int row=0; row<board.length; row++) {
            for (int col=0; col<board[row].length; col++) {
                if(backtrack(col, row, 0, board, words, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean backtrack(int col,int row,int index,char[][] board,char[] words,boolean[][] visited) {
        if (row<0||row>= board.length||col<0||col>=board[row].length||visited[row][col]) {
            return false;
        }
        if (board[row][col] != words[index]) {
            return false;
        }
        if (index==words.length-1) {
            answer = true;
            return true;
        }

        visited[row][col] = true;
        boolean flag = false;
        //오른쪽으로 이동
        if (col + 1 < board[row].length) {
            flag = backtrack(col+1,row,index+1, board,words,visited);
        }
        //위쪽으로 이동
        if (!flag && row + 1 < board.length) {
            flag = backtrack(col,row+1,index+1,board,words,visited);
        }
        //왼쪽으로 이동
        if (!flag && col - 1 >= 0) {
            flag = backtrack(col-1,row,index+1,board,words,visited);
        }
        //위로 이동
        if (!flag && row - 1 >= 0) {
            flag = backtrack(col,row-1,index+1,board,words,visited);
        }
        visited[row][col] = false;

        return flag;
    }
}

배우게 된 점

• 2차원 배열로 한 행씩 반복문 돌며 재귀 돌리는 모 문제와 달리, 이건 상하좌우를 살피며 해당되는 방향으로 조건이 맞으면(원하는 값이 있으면) 재귀를 수행한다.
• 재귀는 값을 맡기는 것, 값을 찾아 재귀 반복 후 단어의 마지막 문자에 도달하면 true 반환
• 어디에도 해당되는 값이 존재하지 않으면 바로 return false
• 함수의 리턴문을 수행 클래스에서 받아, 수행문 리턴해버리기

💡 행 단위로 문자열을 탐색하고, 문자열이 포함되지 않으면 재귀 호출을 사용하여 다음 행으로 넘어가게 코드를 짰었다. 하지만 이런 방식은 문자열이 행별로만 이어져 있을 때 적합하다.

문자열은 행 뿐아니라 열로도 이어져있기 때문에, 보드의 모든 방향으로 탐색하며(위, 아래, 좌, 우), 모든 가능한 방향을 고려하여 문자열을 찾아야 함.

 

 

 

---

 

 

 

처음 풀 때와 두번 째 풀 때

재귀 활용한 점은 비슷하나 느낀 점도 구현하는 방식도 다르다.

이걸 보니 한번 푼 문제도 또 풀어보면 좋을 것 같단 생각이 또 든다.