[DFS/BFS] 미로탐색 (백준 2178)

백준 문제 풀이중 DFS로 풀 수 있을 것 같아서 끙끙댄 문제다.
머리속으로는 DFS로 풀 수 있을 것 같아서 끙끙대다가 그림 한 번 그려보니 왜 이렇게 됐는지 알게 됐다. BFS와 DFS의 개념 정립이 된 순간 같아서 글을 남겨본다.

퍼즐이 위와 같이 주어졌다면

DFS로 풀 경우 아래와 같은 결과가 나오고,

1 8 0 12 13 0 
2 7 0 11 14 0 
3 6 7 10 15 16 
4 5 8 9 0 17

BFS로 풀 경우 아래와 같은 결과가 나온다.

1 2 0 8 9 0 
2 3 0 7 8 0 
3 4 5 6 7 8 
4 5 6 7 0 9 

DFS 코드:

    static void dfs(int x, int y){
        visited[x][y]=true;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<=N && ny>=0 && ny<=M){
                if(map[nx][ny]==1 && !visited[nx][ny]){
                    map[nx][ny] = map[x][y]+1;
                    dfs(nx, ny);
                }
            }
        }
    }

BFS 코드:

    static void bfs(int x, int y){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        visited[x][y]=true;
        while(!q.isEmpty()){
            Node node = q.poll();
            for(int i=0; i<4; i++){
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if(nx>=0 && nx<=N && ny>=0 && ny<=M){
                    if(map[nx][ny]==1 && !visited[nx][ny]){
                        q.add(new Node(nx, ny));
                        visited[nx][ny] = true;
                        map[nx][ny] = map[node.x][node.y]+1;
                    }
                }
            }
        }
    }

머리 속에서는 되는 것 같은데 왜 안되지 싶은 것들은 차분하게 동작과정을 따라가면서 해보면 이해하는데 도움이 되는 것 같다.