DFS 문제와 그 풀이 - (1)

• 해당 문제는 제로베이스 벡엔드 스쿨에서 만든 문제입니다.

문제의 설명

• N x M 크기의 행렬인 board와 문자열 word가 입력으로 들어올 때 행렬 board에서 word를 찾을 수 있는지 확인하는 문제이다.
• 이때 word로 찾아지는 문자열은 모두 인접해 있어야 한다.

 

예시사진

• 예를 들어 위와 같은 board가 주어졌다고 할 때, word로 ABCCED가 들어왔다면 위 사진의 색칠된 것과 같이 찾을 수 있게 되어 true를 반환하게 된다.

 

 

문제의 접근

• word로 주어진 문자열을 찾을 때 모든 문자들이 인접해야 한다는 조건이 있다. 이는 board의 각 칸을 하나의 노드로 생각할때 상하좌우로 간선이 연결된 그래프로 모델링이 가능하다.
• 즉 문제는 이 그래프에서 탐색을 통해 word와 동일한 문자열을 만들어낼 수 있는가를 묻고 있다고 할 수 있다.

public class Practice1 {
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    public static boolean solution(char[][] board, String word) {
        return false;
    }

    public static void main(String[] args) {
        // Test code
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        System.out.println(solution(board, "ABCCED"));
        System.out.println(solution(board, "SEE"));
        System.out.println(solution(board, "ABCB"));
    }
}

• 배열의 각 칸을 순회하면서 해당 배열을 시작점으로 하는 DFS 탐색을 통해 해결할 수 있어 보인다.

public class Practice1 {
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    
    public static boolean solution(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;

        boolean[][] visited = new boolean[row][col];

        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (dfs(board, word, i, j, 0, visited)){
                    return true;
                }
            }
        }

        return false;
    }

    public static boolean dfs(char[][] board, String word, int y, int x, int idx, boolean[][] visited){
        
    }

    public static void main(String[] args) {
        // Test code
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        System.out.println(solution(board, "ABCCED"));
        System.out.println(solution(board, "SEE"));
        System.out.println(solution(board, "ABCB"));
    }
}

• 우선 이동 방향 벡터인 dx와 dy를 만들고 각 칸에 대해 DFS를 수행하여 그 결과가 참이라면, 즉 word로 받은 문자열을 찾았다면 true를 반환하고, 그렇지 않다면 false를 반환하도록 solution 메서드를 구현하였다.
• 이제 dfs를 만들 차례이다. 재귀적으로 만들것이므로 먼저 종료 조건부터 따져야한다.
• 배열의 범위를 넘어가거나, 이미 방문한 노드를 다시 방문하면 안된다. 또한 내가 찾고 있는 문자열의 철자와 현재 방문 중인 노드의 철자가 달라서도 안된다. 즉 이런 상황에서는 모두 종료되어서 빠져나가도록 설계해야한다.
• 위의 필터를 거치고 나서 word의 길이만큼 문자열이 완성되었다면 word와 동일한 문자열이 완성되었다는 것이기 때문에 찾았다는 의미의 true를 반환하면 된다.

public static boolean dfs(char[][] board, String word, int y, int x, int idx, boolean[][] visited){
    int row = board.length;
    int col = board[0].length;

    if (idx == word.length()){
        return true;
    }

    if (y < 0 || y >= row || x < 0 || x >= col){
        return false;
    }

    if (visited[y][x]){
        return false;
    }

    if (board[y][x] != word.charAt(idx)){
        return false;
    }

    return false;
}

• 이제 방문 중인 노드를 방문했다고 visited에 표시한다.
• 이후 상하좌우의 4방향에 대해 모두 dfs를 수행하여 word와 동일한 문자열이 존재하는지 검사한다. 이후 되돌아가면서 방문하기 전의 상태로 만들어야 하기 때문에 visited를 다시 false로 표시하여 방문 전의 상태로 되돌린다(backtrack)

public static boolean dfs(char[][] board, String word, int y, int x, int idx, boolean[][] visited){
    int row = board.length;
    int col = board[0].length;

    if (idx == word.length()){
        return true;
    }

    if (y < 0 || y >= row || x < 0 || x >= col){
        return false;
    }

    if (visited[y][x]){
        return false;
    }

    if (board[y][x] != word.charAt(idx)){
        return false;
    }
    
    visited[y][x] = true;
    for (int i = 0; i < 4; i++){
        if (dfs(board, word, y + dy[i], x + dx[i], idx + 1, visited)){
            return true;
        }
    }
    visited[y][x] = false;

    return false;
}