[A100C_day 3] Leetcode 79. Word Search (java)

정답 코드 

 

class Solution {
    private static final int[][] DIRECTION = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        for(int y = 0; y < m; ++y){
            for(int x = 0; x < n; ++x){
                if(searchWord(y, x, board, visited, word)) return true;
            }
        }
        
        return false;
    }
    
    public boolean searchWord(int y, int x, char[][] board, boolean[][] visited, String word){
        
        if(y < 0 || y >= board.length || x < 0 || x >= board[0].length) return false; 
        if(visited[y][x]) return false;
        if(board[y][x] != word.charAt(0)) return false; 
        
        if (word.length() == 1) return true;
        visited[y][x] = true;
        
        for(int[] direction : DIRECTION){
            int neighborY = y + direction[0];
            int neighborX = x + direction[1];
    
            if(searchWord(neighborY, neighborX, board, visited, word.substring(1))) return true;
        }
        
        visited[y][x] = false;
        
        return false;
    }
}

 

---

사고 과정

 

오늘은 dp 풀려 했는데, 배열 조금 더 깊게 들어가 보는거로!

 

DFS, BackTracking, Recursive 등등 핵심 개념들 골고루 섞인 문제로..

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

다음과 같이 생긴 이차원 배열에서,

 

 

상하좌우 인접한 부분을 연결했을 때 원하는 글자가 있는지 아닌지 여부를 출력하면 되는 문제!

 

target : ABCCED -> 단어 있음!

 

 

길 찾기 게임을 한다고 가정했을 때, 캐릭터를 이동시키기 위해서는 이동 명령을 내려주는 방향키가 필요하다. 

 

문제에 들어가기 앞서, 상하좌우로 이동하며 탐색하기 위한 방향키(?) 역할을 하는 이차원 상수 배열을 하나 생성해주자. 

 

    private static final int[][] DIRECTIONS = {
        { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 }
    };

 

- 편안 - 

 

다음으로, 각 인덱스를 순회하면서, 해당 단어를 찾는 함수 searchWord()를 실행시켜주면 될 것 같은데,,

 

int m = board.length;
int n = board[0].length;

for(int y = 0; y < m; ++y){
	for(int x = 0; x < n; ++x){
    	
        //searchWord() 실행!!
        
    }
}

 

 

searchWord를 실행하기 앞서, 각 인덱스에서 상하좌우로 움직이게 되는데, 중복이 발생하는 경우가 있다. 

 

위의 이미지에서 target이 "ABA"라면, 해당 단어는 존재하지 않으므로 false를 출력해야 하지만 [[0][0],[0][1],[0][0]] 이렇게 처음 검사했던 A를 중복해서 인식하여 true를 반환할 수도 있다는 소리..

 

따라서 각 인덱스가 검사 완료한 인덱스인지를 나타내는, board와 동일한 크기의 boolean값 배열 visited를 생성해줬다. 

 

boolean[][] visited = new boolean[m][n];

 

(java에서 배열을 생성과 동시에 자동으로 자신의 타입에 해당하는 기본값으로 초기화된다! (int -> 0, boolean -> false))

 

---

 

이제 searchWord()를 만들어보려 하는데,, 

 

우선 백트래킹 알고리즘의 핵심은 가능한 모든 경우의 수를 고려하지 않고, 손절(?)할 여지가 있는 경우의 수는 즉시 손절할 수 있다는 점이므로,, 이 손절포인트(?) 를 먼저 정의해보자. 즉, 해당 메서드에서 false를 리턴해야 하는 경우를 정의해보자. 

 

1. 상하좌우로 이동하다가 board의 영역 밖으로 넘어갔을 때. 
2. visited 배열을 참고하여, 이미 지나온 길일 때.
3. 해당 인덱스의 문자가 target의 문자와 다를 때. 

 

 

이 세가지 경우만 고려하면 될 것 같다. 

이를 코드로 표현하면, 

 

 public boolean searchWord(int y, int x, char[][] board, boolean[][] visited, String word){
        
        if(y < 0 || y >= board.length || x < 0 || x >= board[0].length) return false; // board범위를 벗어날 때.
        if(visited[y][x]) return false; // 이미 지나온 길일때
        if(board[y][x] != word.charAt(0)) return false; // 비교하려는 target 문자와 다를 때
       
    }

 

이 searchWord를 재귀함수를 통해 상하좌우 이동하면서 실행해야 하므로,, 위에서 방향키로 설정해뒀던 DIRECTION을 이용하면 다음과 같이 코드를 작성할 수 있다. 

 

 public boolean searchWord(int y, int x, char[][] board, boolean[][] visited, String word){
        
        if(y < 0 || y >= board.length || x < 0 || x >= board[0].length) return false; 
        if(visited[y][x]) return false; 
        if(board[y][x] != word.charAt(0)) return false; 
        
        for(int[] direction : DIRECTION){
            int neighborY = y + direction[0];
            int neighborX = x + direction[1];
    
            if(searchWord(neighborY, neighborX, board, visited, word.substring(1))) return true;
            //substring메서드로 word를 한글자씩 줄여가며(슬라이싱처럼) 각각 순차적으로 검사!
        }
    }

 

앞선에서 false에 대한 경우는 모두 고려했으므로, 이 경우에 걸러지지 않는 최종 문자는 true를 반환해야 할 것이다. 이를 반영하면 

 public boolean searchWord(int y, int x, char[][] board, boolean[][] visited, String word){
        
        if(y < 0 || y >= board.length || x < 0 || x >= board[0].length) return false; 
        if(visited[y][x]) return false;
        if(board[y][x] != word.charAt(0)) return false; 
        
        if (word.length() == 1) return true; // 위의 케이스에 해당되지 않는 문자는 검사하려는 word의 문자일 수밖에!
        
        for(int[] direction : DIRECTION){
            int neighborY = y + direction[0];
            int neighborX = x + direction[1];
    
            if(searchWord(neighborY, neighborX, board, visited, word.substring(1))) return true;
        }
    }

 

마지막으로 검사를 완료한 인덱스에 관해서는 검사한 부분이라는 정보를 남겨둬야 하므로 visited 배열의 해당 인덱스 값을 true로 변경해야한다!!

(후에 다시 false로 초기화하는 것도 잊어서는 안된다.)

 

이를 코드로 표현하면

 

 public boolean searchWord(int y, int x, char[][] board, boolean[][] visited, String word){
        
        if(y < 0 || y >= board.length || x < 0 || x >= board[0].length) return false; 
        if(visited[y][x]) return false;
        if(board[y][x] != word.charAt(0)) return false; 
        
        if (word.length() == 1) return true; 
        visited[y][x] = true; // 지나온 길임 표시!
        
        for(int[] direction : DIRECTION){
            int neighborY = y + direction[0];
            int neighborX = x + direction[1];
    
            if(searchWord(neighborY, neighborX, board, visited, word.substring(1))) return true;
        }
        
        visited[y][x] = false; //board 특정 인덱스에 대한 검사가 종료되면 다시 false로 초기화!
    }

 

 

그렇게 탄생한 최종 코드.. 

 

class Solution {
    private static final int[][] DIRECTION = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        for(int y = 0; y < m; ++y){
            for(int x = 0; x < n; ++x){
                if(searchWord(y, x, board, visited, word)) return true;
            }
        }
        
        return false;
    }
    
    public boolean searchWord(int y, int x, char[][] board, boolean[][] visited, String word){
        
        if(y < 0 || y >= board.length || x < 0 || x >= board[0].length) return false; 
        if(visited[y][x]) return false;
        if(board[y][x] != word.charAt(0)) return false; 
        
        if (word.length() == 1) return true;
        visited[y][x] = true;
        
        for(int[] direction : DIRECTION){
            int neighborY = y + direction[0];
            int neighborX = x + direction[1];
    
            if(searchWord(neighborY, neighborX, board, visited, word.substring(1))) return true;
        }
        
        visited[y][x] = false;
        
        return false;
    }
}

 

배열, DFS, 백트래킹, 재귀 등 알고리즘 종합 선물 세트 같았던 문제!