백준 2206번 벽 부수고 이동하기 G3 - BFS

 

 

ㅋㅋ 쾅ㅋ

 

 

G3.. 이놈 조건이 독특하다.

단순히 최단 거리를 구하는 알고리즘 + 벽을 1번 뚫을 수 있다가 조건이다.

근데 저 조건 하나가 왤케 무겁지

 

어떻게 뚫은거 체크하지~? -> 객체에 걍 boolean으로 줬다.

 

그리고 하나 더

 

visited를 3차원으로 선언해 주었다. 이게 풀면서도 아! 이거 생각 많이해야겠다 했는데 다행히 방법이 맞았다.

벽을 부수는 순간 다른 공간으로 인식해야하기 때문인데, 지도에 지름길이 하나 생길 수도 안부수는게 더 빠를 수도 있는 경우가 생기니까.

 

결국 판단하는 기준은 부수는 위치로 나눠야하며 만약 부순 이후라면 다르게 경로를 탐색해주어야 한다.

이런 조건을 사용하지 않는다면 부수고 새로 열리는 길이 더 효율적인지 판단해서 넣어도 답이 나올것 같다..

하지만 지금은 졸려서리 빨리 정리핳곡ㄱ자고싶어엎퍼퍼

 

 

import java.io.*;
import java.util.*;
 
public class Main { // Boj_2206_벽 부수고 이동하기
 
    static class Me {
        int x, y, dist;
        boolean break_wall;
 
        public Me(int x, int y, int dist, boolean break_wall) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.break_wall = break_wall;
        }
    }
 
    static int N, M, answer;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] map;
    static boolean[][] visit;
 
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        answer = -1;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                if (input.charAt(j) == '1') {
                    map[i][j] = true; // 갈수 있음 == true;
                }
            }
        }
 
        answer = bfs(0, 0);
        System.out.println(answer);
    }
 
    public static int bfs(int x, int y) {
        boolean[][][] visited = new boolean[N][M][2];
        Queue<Me> queue = new LinkedList<>();
        queue.offer(new Me(x, y, 1, false));
        visited[x][y][0] = true; // 벽 부쉈는지 체크용
 
        while (!queue.isEmpty()) {
            Me cur = queue.poll();
            if (cur.x == N - 1 && cur.y == M - 1) {
                return cur.dist; // 한번에 도착하는 경우.
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (range_chk(nx, ny)) {
                    boolean wall = map[nx][ny];
                    boolean canBreakWall = !cur.break_wall && wall; // 벽이 있고 아직 한번도 부수지 않았을때
 
                    if (wall && canBreakWall && !visited[nx][ny][1]) { // 벽을 부수는 case
                        queue.offer(new Me(nx, ny, cur.dist + 1, true)); // 더이상 벽을 부수지 못함.
                        visited[nx][ny][1] = true;
                    } else if (!wall && !visited[nx][ny][cur.break_wall ? 1 : 0]) { // 일반적인 case
                        queue.offer(new Me(nx, ny, cur.dist + 1, cur.break_wall));
                        visited[nx][ny][cur.break_wall ? 1 : 0] = true;
                    }
                }
            }
        }
 
        return -1;
    }
 
    public static boolean range_chk(int x, int y) {
        return 0 <= x && 0 <= y && x < N && y < M;
    }
}

 

한방에 풀어서 짜릿.. 저릿