ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [백준/JAVA] 2206 벽 부수고 이동하기
    ETC/Algorithm 2023. 5. 27. 01:45

    문제

    문제 인식

    변수 상황

    N * M의 행렬로 표현되는 맵이 있고, 0은 이동가능 1은 이동 불가능한 벽으로 표현된다.
    이동은 (1,1)에서 시작하며, 도착점은 (N,M)으로 고정되어있다.
    하지만 변수 상황이 주어지는데


    간단히 기존 BFS 문제에서 벽을 한번은 통과할 수 있다는 것이다.

    그렇다면 다른 BFS 문제와 형태는 같지만 벽을 한 번 통과 가능하다는 점을 어떻게 구현할 것인가가 문제의 핵심으로 인식했다.

    실패한 문제 해결

    처음 생각한 방법은, BFS를 재귀를 통해 다시 불러오는 방식을 생각하였다.

    첫 시작은 벽 부신 값을 false로 갖고 시작
    재귀를 통해 한번 벽을 부셨다면 true 값을 주고 반복하여 진행하였다.

    여기서 문제가 발생하는데,
    벽을 한번 부신 경우가 그냥 정상적인 길로 가도 거리 값은 동일한데 먼저 진행된 경우였다.
    이 경우 visited 값이 미리 true로 입력되어, 벽을 한 번 부실 수 있는 기회를 날리고 시작하게 되는 것이다.

    이 경우에서 이후 풀이인 visited를 3차원 배열로 구현하여 한번 더 진행하였다면 성공하였겠지만,
    새로운 풀이로 다시 진행하였다.


    풀이

    주의점

    도중에 한 개의 벽을 부신경우 더 이상 부실 수 없다.

    당연하게도 벽은 한번 밖에 부시질 못한다. 그럼 true, false 또는 0,1로 표현 가능하다.

    벽을 부시고 이동한 경우와, 벽을 안부시고 이동한 경우의 거리값이 동일 할 수 있다.

    위의 실패한 해결의 내용과 동일하다. 이를 해결하기 위해 visited를 3차원 배열로 구현하여 해결가능하다.

    map을 입력 받을 때, char 값으로 입력받는다.

    여태 문제 풀면서 고려 해왔지만,

    String line = br.readLine();

    으로 값을 입력 받아 charAt() 으로 값을 char 형으로 받아오므로 0,1이 정수 형이 아니다.
    꼭 48 값을 빼주자


    코드

    코드 해석

    • BFS 알고리즘을 사용하였다.
    • 다음 이동할 곳이 그냥 길인 경우 그리고, 다음 이동할 곳이 벽인데 벽을 부지 않은 경우를 고려한 조건문을 설정해서 해결하였다.
    • 다른 BFS 문제와 다르게, map 자체의 값의 변화를 주지 않고 해결하였다. 자체 Pos 클래스에 x,y,이동한 거리, 벽을 부신 여부를 저장한다.
    • 시작하는 칸과 끝나는 칸을 포함해서 센다. 시작부터 cnt는 1로 시작한다.
    • 큐에서 값을 꺼내오자마자 좌표값이 도착점이면 현재 까지의 이동거리 값(cnt)를 리턴한다.
    • 큐에 비어있게 되었을 때까지 도착지점에 도달하지 못한 경우는 불가능한 경우이다. -1을 리턴하도록 지정해둔다.

    제출 코드

    import java.io.*;
    import java.util.*;
    
    class Main {
    
        static int N, M;
        static Queue<Pos> q = new LinkedList<>();
        static boolean[][][] visited;
        static int[][] map;
        static int[] opsX = {1, -1, 0 ,0};
        static int[] opsY = {0, 0, 1, -1};
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        static StringTokenizer st;
    
        static class Pos {
            int x;
            int y;
            int cnt;
            int hit;
    
            public Pos(int x, int y, int cnt, int hit) {
                this.x = x;
                this.y = y;
                this.cnt = cnt;
                this.hit = hit;
            }
        }
    
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
    
            map = new int[N][M];
            visited = new boolean[N][M][2];
    
            for (int i = 0; i < N; i++) {
                String line = br.readLine();
                for (int j = 0; j < line.length(); j++) {
                    map[i][j] = line.charAt(j) - 48;
                }
            }
            bw.write(String.valueOf(bfs(new Pos(0,0,1,0))));
            bw.flush();
        }
    
        public static int bfs(Pos node) {
            q.offer(new Pos(node.x, node.y, node.cnt, node.hit));
            visited[node.x][node.y][node.hit] = true;
    
            while (!q.isEmpty()) {
                Pos now = q.poll();
    
                if (now.x == N-1 && now.y == M-1) {
                    return now.cnt;
                }
    
                for (int i = 0; i < 4; i++) {
                    int newX = now.x  + opsX[i];
                    int newY = now.y  + opsY[i];
    
                    if (checkRange(newX, newY)) {
                        // 다음 이동할 곳이 그냥 길인 경우
                        if (map[newX][newY] == 0 && !visited[newX][newY][now.hit]) {
                            q.offer(new Pos(newX, newY, now.cnt+1, now.hit));
                            visited[newX][newY][now.hit] = true;
                        }
    
                        // 다음 이동할 곳이 벽인데 벽을 부지 않은 경우
                        if (now.hit == 0 && map[newX][newY] == 1 && !visited[newX][newY][now.hit]) {
                            q.offer(new Pos(newX, newY, now.cnt+1, now.hit+1));
                            visited[newX][newY][now.hit] = true;
                        }
                    }
                }
            }
            return -1;
        }
    
        public static boolean checkRange(int x, int y) {
            return -1 < x && x < N && -1 < y && y < M;
        }
    }

    댓글

Designed by black7375.