[leetcode] Word Search

문제

• 문제 링크
• m x n 크기의 board와 문자열 word가 주어진다. word가 board 안에 있는지 확인해야 한다. board 안에서 수직/수평으로 인접한 문자들을 연결해서 word가 나올 수 있으면 word는 board 안에 있다고 할 수 있다.
• 제약 조건
  • 1 <= m, n <= 6
  • 문자열 크기: 1 <= word.length <= 15
  • board와 word는 소문자, 대문자의 알파벳으로 구성되어 있다.

풀이

풀기 전

• bfs로 풀면 되겠지 하고 풀었는데 답이 안 나왔다. bfs는 한 번 방문한 곳은 다시 방문하지 않는데, 해당 문제에선 이미 방문했던 곳을 또 방문하는 게 옳을 수도 있었다. 생각해보니 bfs는 최단 거리 구하는 문제에서 사용하는데 요 문제랑은 안 맞는 거 같았다.
• dfs로 노선을 틀었다. 다시 방문하지 않는 곳은 현재 지나온 경로에 있는 문자뿐이기 때문에 dfs로 푸는 게 맞았다. board를 순회하다가 문자열 word의 첫 문자와 같은 문자가 나오면 dfs를 시작하도록 했다.

코드

class Solution {
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};

	// i와 j는 방문한 위치이다.
    // wordChar는 문자열 word를 배열로 만든 거다.
    // depth는 현재 탐색 중인 깊이다.
    private boolean dfs(char[][] board, int i, int j, char[] wordChar, int depth) {
    	// depth가 word의 길이와 같다는 건 word 끝까지 잘 찾았다는 뜻이므로 true 반환한다.
        if (depth == wordChar.length)
            return true;

        int ny, nx;
        char tmp;
        for (int k=0; k<4; k++) {
        	// 다음에 방문할 인덱스를 구한다.
            ny = i + dy[k];
            nx = j + dx[k];

			// 다음에 방문할 인덱스가 board 범위를 벗어나면 continue
            if (ny < 0 || ny >= board.length || nx < 0 || nx >= board[0].length)
                continue;
            // 다음에 방문할 문자가 찾아야하는 word의 문자와 일치하지 않으면 continue
            if (board[ny][nx] != wordChar[depth])
                continue;

			// board를 방문 여부하는 배열로 사용하기 위해 기존 값을 임시로 저장해놓고
            // 방문했다는 표시로 '*'을 넣는다.
            tmp = board[ny][nx];
            board[ny][nx] = '*';
            // 다음 위치로 탐색 진행
            if (dfs(board, ny, nx, wordChar, depth + 1))
                return true;
            // 방문 해제하기 위해 기존 값을 다시 넣어준다.
            board[ny][nx] = tmp;
        }
        return false;
    }

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

        char tmp;
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
            	// board의 문자가 word의 첫 번째 문자와 같으면 dfs 진행한다.
                if (board[i][j] == word.charAt(0)) {
                    tmp = board[i][j];
                    board[i][j] = '*';
                    if (dfs(board, i, j, wordChar, 1))
                        return true;
                    board[i][j] = tmp;
                }
            }
        }
        return false;
    }
}

푼 후

• 생각 많이 안하고 bfs로 풀었다가 시간 좀 버렸다. 최단 거리면 bfs, 해당 문제처럼 탐색했던 곳을 다시 탐색하는 거면 dfs로 생각하자.
• 처음에 runtime 시간이 하위 37%길래 다른 사람들은 뭔가 다르게 했나 봤는데 큰 차이가 없었다. 그래서 아래 방식으로 좀 고쳤더니 상위 11%로 바꼈다.
  • 방문 체크하는 visit 배열을 따로 두지 않고 board 배열을 재사용
  • 문자열 word를 char[] 배열로 변경하여 사용