[DFS 알고리즘 연습문제] 2차원 배열에서 문자열 탐색하기(word search)

문제 설명

다음과 같은 2차원 문자열 배열이 주어질 때, 

[A, B, C, E]

[S, F, C, S]

[A, D, E, E]

 

지정 문자열 "ABCCED" 에 대하여 위의 배열에서 찾아서  존재하는지를 반환하는 dfs 풀이를 작성하시오.

단, 지정 문자열을 찾을 때 문자열은 연결되어있어햐 한다.

 

결과 : true

 

나의 풀이

public static void main(String[] args) {
        String[][] grid = {
            {"A","B","C","E"},
            {"S","F","C","S"},
            {"A","D","E","E"}
        };
        
        Main m = new Main();
        String word = "ABCCED";
        System.out.println(m.solve(grid, word));
    }
    
    int m, n;
    public boolean solve(String[][] grid, String word) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return false;
        
        m = grid.length;
        n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(dfs(grid, visited, i, j, 0, word)){
                    return true;
                }
            }
        }
        return false;
    }
    
    int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    public boolean dfs(String[][] grid, boolean[][] visited, int x, int y, 
                       int start, String word) {
        if (word.length() == start) return true;
        if (x < 0 || x >= m || y < 0 || y >= n) return false;
        if (visited[x][y] == true) return false;
        if (!grid[x][y].equals(word.substring(start, start+1))) return false;
        
        visited[x][y] = true;
        
        for(int[] dir : dirs) {
            int x1 = dir[0] + x;
            int y1 = dir[1] + y;
            
            if(dfs(grid, visited, x1, y1, start+1, word)) {
                return true;
            }
        }
        visited[x][y] = false;
        return false;
    }

Int[][] dirs : 이렇게 사방으로 무언가를 검사해야할것 같은 문제들은 사방으로 돌릴 변수를 하나 선언해놓는다. 메인의 dfs 로직에서 사방으로 조회하기 위해 사용될 변수다. 

-> 또한 dirs for문 내부에서는 argument로 받은 좌표들을 조합하여 새로운 좌표를 생성하여 새로운 dfs에 전달해야한다. 

-> 그 for문 내부에서 dfs는 재귀호출을 한다.

 

이번 문제는 이전처럼 grid 라는 배열을 직접 조작하여 처리하는 것이 아닌 그림자 배열(visited)를 생성하여 grid가 다녀간 위치에 따라 true값을 넣어주었다. 이점을 이해하기가 좀 어려웠지만 자주들여다보니 꺠닫게 된 케이스다.

 

Dfs 메소드의 맨 처음로직 => if(word.length() == start) return true; 

이 문장이 제일 처음 오는 이유는 dfs가 마지막 문자인 D를 통과하고 true를 밷고 다음 문자열을 찾아 들어갈 때 start는 word의 length가 되어있을 것이다. 따라서 이는 탈출해야하는 문장이며 결국 지금까지 지나왔던 모든 if문들을 true로 뚫고 들어가 return true를 연발할 것이다.

If(dfs(grid, visited, x1, y1, start+1, word)) => return true * word.length 번 진행할 것이다.

 

Dfs 메소드의 마지막에 Visited[x][y] = false로 지정해 놓는 이유는 다시 모든것이 되돌아 가야하는 단계이기 때문에 visitied에 대한 정보도 수정되어야 한다. 즉 ABCCED를 찾아가다가 실패하여 return false를 연발하고 모든 visited들은 false로 수정되어야 다음 i , j 에 대하여 같은 로직을 수행할 수 있다.

 

풀이를 좀 장황하게 순서없이 설명한 감이 있지만 문단마다 내가 이해하지 못하여 어려움을 겪었던 부분들을 적어두었다. 나중에 다시볼때도 이 위주로 보면 될 것 같다.