[Leetcode] 79. Word Search (java)

문제

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

문제설명

알파벳이 채워져있는 이차원 배열 board와 찾아야하는 문자열 word가 주어진다.
이 때 board에서 이웃한(가로 또는 세로로) 문자를 이어 word를 만들 수 있는지 체크하는 함수이다.

해결방법

1. 이중 포문을 이용하여 board를 탐색한다.
2. search 함수는 board에서 word[n]을 찾는 함수이다. (이웃한 글자여야함.)
   2-1. 우선, n은 word의 인덱스로 만약 n이 word.length와 같다면 이미 board 내에 word와 일치하는 글자 탐색에 성공한 것이므로 true를 반환한다.
   2-2. i, j 는 board[i][j]로서 0이하의 숫자나 board의 행, 열 길이를 넘는 경우 false 를 반환한다.
   2-3. 이미 방문한 위치인 경우 false 를 반환한다.
   2-4. 현재 위치 board[i][j] 가 word[n] 이 아닌 경우에도 false 를 반환한다.
   2-1 ~ 2-4 까지 검증한 후에는 현재 위치가 찾는 알파벳(word[n]) 이므로 visited[i][j] = true 로 변경해준다.
   이 후, word 전체 문자열을 찾기 위하여 위,아래,좌,우 글자가 word[n+1]과 일치하는지 찾기 위하여
   search(board, word, n+1, i-1, j) || search(board, word, n+1, i+1, j) || search(board, word, n+1, i, j-1) || search(board, word, n+1, i, j+1) 을 실행해준 후 이 결과를 반환한다.
   이 때, 주의해야할 점은 결과가 만약 true로 반환된다면 일치하는 문자열을 찾은 것이지만 만약 false로 반환된다면 다시 word를 찾는 과정을 수행해야하므로 visited[i][j] = true로 바꿔주었던 것을 다시 visited[i][j] = false 로 변환해주어야한다.

코드

// Word Search
public class pb79 {
	boolean[][] visited;
	
	public boolean exist(char[][] board, String word) {
		if(word.length() == 0) return true;
		
		int row = board.length;
		int col = board[0].length;
		visited = new boolean[row][col];
		
		for(int i=0; i<row; i++) {
			for(int j=0; j<col; j++) {
				if(search(board, word, 0, i, j)) return true;
			}
		}
		return false;
    }
	
	boolean search(char[][] board, String word, int n, int i, int j) {//n : word의 인덱스
		if(n == word.length()) return true;
		
		if(i<0 || j <0 || i>= board.length || j>= board[0].length) return false;
		if(visited[i][j]) return false;
		if(word.charAt(n) != board[i][j]) return false;
		
		// 일치하는 칸을 찾은 경우
		visited[i][j] = true;
		boolean result = search(board, word, n+1, i-1, j) || search(board, word, n+1, i+1, j) || search(board, word, n+1, i, j-1) || search(board, word, n+1, i, j+1); 
		// 만약 연속된 연산에서 word를 찾지 못하면  해당 칸을 다시 계산해야하므로 false로 갱신해준다.
		if(result != true) visited[i][j] = false;
		return result;
	}
	
}