[JAVA] 백준 2206번 : 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M, min;
    static char[][] map;
    static boolean[][][] visit;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visit = new boolean[2][N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }
        min = bfs(new Pos(0, 0, 1, 0));
        System.out.println(min);
    }

    private static int bfs(Pos start) {
        Queue<Pos> queue = new LinkedList<>();
        queue.add(start);
        visit[0][start.x][start.y] = true;
        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            if(now.x == N-1 && now.y == M-1){
                return now.cnt;
            }
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= N || ny >= M || visit[now.breakWall][nx][ny]) continue;
                if(map[nx][ny] == '1' && now.breakWall == 1) continue; //벽 있음 + 이미 한 번 부숨
                if(map[nx][ny] == '1' && now.breakWall == 0){ //벽 있음 + 부술 기회 있음
                    queue.add(new Pos(nx, ny, now.cnt + 1, 1)); //부순거 표시
                    visit[1][nx][ny] = true;
                    continue;
                }
                if (map[nx][ny] == '0') {
                    queue.add(new Pos(nx, ny, now.cnt + 1, now.breakWall));
                    visit[now.breakWall][nx][ny] = true;
                }
            }
        }
        return -1;
    }

    private static class Pos {
        int x; int y; int cnt; int breakWall;

        Pos(int x, int y, int cnt, int breakWall) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.breakWall = breakWall;
        }
    }
}

💡 BFS

풀이

• 주어진 벽들을 하나씩 없애는 경우를 생각할 것
• BFS로 진행하되, 1을 만나면 해당 벽을 부순적이 있는지 체크
  • 부순적이 없는 경우 -> 벽 부수는 경우 / 벽 부수지 않는 경우 2가지 경우 각각 객체 생성해 진행
  • Pos 클래스에 벽 부수는 기회 사용했는지 여부 검사하는 필드 하나 추가하는 방식으로...
  • (N, M) 도달한 경우 최솟값 갱신
• 하지만 위 경우, 벽을 뚫고 가서 visit 배열을 체크 했는데 끝까지 도달하지 못한 경우 문제 발생 (벽을 부수지 않고 해당 경우에 돌아서 가는 경우도 같이 막히게됨)
  
  • 예외 사항을 주기 >> 한 번도 벽을 깨지 않은 경우 visit여도 통과할 수 있게 함 
  • visit[][] 체크 배열을 3차원으로 확장하자 => breakWall이 0번인 경우 visit[0][x][y]에 체크, breakWall이 1번인 경우 visit[1]][x][y]에 체크 
    • 벽을 부순 경우 / 아닌 경우 분리 가능하게 됨