[알고리즘 PS] 백준 2206번 벽 부수고 이동하기 자바 문제풀이

문제

해당 포스팅은 백준의 2206번 벽 부수고 이동하기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

2206번: 벽 부수고 이동하기

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

최단 거리라 BFS로 해결할 수 있는 문제이다.

 

지금까지 해결했던 BFS 에서는 제일 이해가 힘들었던 문제다.

 

처음은 브루트포스로 벽을 뚫고 bfs 를 수행했는데 계속해서 시간초과가 나와서 결국 블로그의 힘을 빌렸던 문제다.

 

정답 코드

public class Main {

    private static int n;
    private static int m;
    private static int[][] visited;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");

        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);

        visited = new int[n][m];
        arr = new int[n][m];

        for(int i = 0; i < n; i++) {

            String[] s = br.readLine().split("");

            for(int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
                visited[i][j] = Integer.MAX_VALUE;
            }
        }

        bw.write(String.valueOf(bfs()));

        bw.flush();
        bw.close();
    }

    private static int bfs() {

        int[] xPos = {1, -1, 0, 0};
        int[] yPos = {0, 0, 1, -1};

        Queue<Position> queue = new LinkedList<>();

        queue.add(new Position(0, 0, 1, 0));
        visited[0][0] = 0;

        while(!queue.isEmpty()) {
            Position front = queue.remove();

            if(front.x == m - 1 && front.y == n - 1) return front.depth;

            for(int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];
                if(!(0 <= xx && xx < m && 0 <= yy && yy < n)) continue;

                if(visited[yy][xx] > front.breakWall) { // 방문하지 않는 노드만

                    if(arr[yy][xx] == 0) {
                        queue.add(new Position(xx, yy, front.depth + 1, front.breakWall));
                        visited[yy][xx] = front.breakWall;
                    }else {
                        if(front.breakWall == 0) {
                            queue.add(new Position(xx, yy, front.depth + 1, front.breakWall + 1));
                            visited[yy][xx] = front.breakWall + 1;
                        }
                    }
                }
            }
        }

        return -1;
    }

    private static class Position {
        int x, y, depth, breakWall;

        Position(int x, int y, int depth, int breakWall) {
            this.x = x;
            this.y = y;
            this.depth = depth;
            this.breakWall = breakWall;
        }
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.