[백준 2206] 벽 부수고 이동하기 (Java, BFS)

 

 

[백준 2206] 벽 부수고 이동하기 (Java, BFS)

 

문제 출처 : 링크

2206번: 벽 부수고 이동하기

 

지난번에 포스팅한 미로만들기와 유사한 방법으로 접근해야하는 문제다.

이 문제의 정답률은 훨씬 낮은데, N과 M의 값이 1000으로 큰 값을 가지고 있어서 시간초과에 빠지기 쉬운 문제다. 벽을 단 한번만 부실 수 있으므로, 벽을 모든 경우의 수로 부시면서 접근했다간 절대 풀 수 없는 문제

 

 

보통 boolean으로 visit 체크를 하지만, 이처럼 최단 경로에 대한 값을 가져가기 위해선 int형으로 만들어 갱신해나가는 방법으로 접근해야 한다.

 

애초에 class를 선언할 때 y와x 좌표와 함께 이동거리와 공사횟수를 함께 저장해서 가져간다.

static class Place {
    int y;
    int x;
    int dis; // 이동거리
    int drill; // 공사횟수
    
    public Place(int y, int x, int dis, int drill) {
        this.y = y;
        this.x = x;
        this.dis = dis;
        this.drill = drill;
    }
}

BFS를 진행하면서 Queue에 넣을 때, 이동거리는 늘려주고, 벽은 단 한번만 부실 수 있기 때문에 공사횟수를 가져가면서 성립할 때만 add 해주면 된다.

 

결국 Queue가 돌다가 마지막 도착지에 해당하는 (N-1,M-1) 좌표 값이 poll 되면, 거기에 들어있는 dis 값을 가져와서 출력해주면 된다.

 

visit 배열의 값은 공사횟수를 나타내므로, 만약 다음에 나온 공사횟수 값이 기존에 갖고 있던 값보다 작거나 같으면 굳이 Queue에 추가하지 않고 넘어가도 된다.

 

Queue에 넣는 조건은 map에 저장된 값을 보고 0과 1일 때로 나누어 진행한다.

0은 그냥 지나갈 수 있는 곳이므로 이동거리 값만 늘려서 Queue에 넣어주고,

1은 벽이기 때문에 poll했던 공사횟수가 0일 때만 진행할 수 있다. (이전에 공사를 안했던 상태에서만) 따라서 이때 이동거리와 공사횟수를 증가시켜서 Queue에 넣어준다.

 

이런 유형의 문제는 말만 바꿔서 다양하게 나오므로 꼭꼭 익혀두면 좋다.

 

1. Class 선언 시 내가 필요한 것을 변수로 만들어서 가지고 다니기

2. 방문 배열을 boolean이 아닌 int형으로 만들고, 무한대로 초기화 시켜두기

3. BFS안에서 돌면서 상하좌우 체크하며 이동하면, 결국 똑같은 위치를 여러번 탐색하게 됨. 이때 방문 배열의 최소 값을 계속 가져가는 걸 기억하자!

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main_2206_ {
    
    static class Place {
        int y;
        int x;
        int dis; // 이동거리
        int drill; // 공사횟수
        
        public Place(int y, int x, int dis, int drill) {
            this.y = y;
            this.x = x;
            this.dis = dis;
            this.drill = drill;
        }
    }
 
    static int N,M,ans;
    static int[][] map, visit;
    
    static int[] dy = {-1,1,0,0}; // 상,하,좌,우
    static int[] dx = {0,0,-1,1};
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        
        N = Integer.parseInt(str[0]); // 행
        M = Integer.parseInt(str[1]); // 열
        
        map = new int[N][M]; // 초기화
        visit = new int[N][M]; // 초기화
        
        for (int i = 0; i < N; i++) {
            str = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                visit[i][j] = Integer.MAX_VALUE; // 무한대로 초기화
            }
        }
        
        ans = Integer.MAX_VALUE;
        
        bfs(0,0); // 출발점에서 bfs 시작
        
        if(ans == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(ans);;
    }
    
    public static void bfs(int y, int x) {
        
        Queue<Place> q = new LinkedList<>();
        
        q.add(new Place(y, x, 1, 0)); // y좌표, x좌표, 이동거리, 공사횟수
        visit[y][x] = 0; // 처음 공사횟수
        
        while(!q.isEmpty()) {
            
            Place p = q.poll();
            
            // 도착지점 만나면 종료
            if(p.y == N-1 && p.x == M-1){
                ans = p.dis;
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                
                if(ny<0 || nx<0 || ny>=N || nx>=M) continue;
                
                if(visit[ny][nx] <= p.drill) continue;
                
                if(map[ny][nx] == 0) { // 벽이 아닐 때
                    visit[ny][nx] = p.drill;
                    q.add(new Place(ny, nx, p.dis+1, p.drill));
                }
                else { // 벽일 때
                    if(p.drill == 0){
                        visit[ny][nx] = p.drill + 1;
                        q.add(new Place(ny, nx, p.dis+1, p.drill+1));
                    }
                }
            }
            
        }
        
    }
 
}