백준[자바]_2206_벽부수고이동하기_BFS_너비우선탐색

오늘은 백준 단계별로 문제풀기 카테고리 중에서 그래프 순회로 분류되어 있는 문제를 풀어보았다. 최근에 그래프 탐색문제로 너비우선탐색 문제를 많이 풀이해왔는데, 이번 문제는 생각보다 까다로웠다. 

[ 문제 분석 ] 

1. 시작점과 도착점은 벽이 없음이 보장된다. 
2. 시작점과 도착점을 포함해서 이동 거리의 최소값(최단거리)를 도출한다. 
3. 이때 단 한 번의 벽은 부술 수 있다. 
4. 도착점에 도달할 수 있는 경우는 최단거리를, 도달할 수 없으면 -1을 출력한다.

 

[ 오답노트 ]

• 처음에는 그렇게나 골치를 썩이던 벽을 뚫을 수 있다는 말에 반가웠지만 막상 구현에 앞서보니 어떤 벽을 뚫어야 최단거리가 가능할까? 라는 생각을 하다가, 이렇게 생각하기엔 경우의 수가 너무 많아서 도달달 수 있는지 없는지를 판단하기로 했다. 
• 위를 구현하기 위해 map을 입력받을 때, 따로 큐를 생성해놓고 값이 1일때, 즉 벽이 있을때 해당 좌표를 큐에 추가한 다음, 새로운 반복문에서 큐에서 요소를 하나씩 꺼내면서 해당 값을 0으로 바꾼 후(벽을 부순 후) BFS탐색을 반복하는 등 모든 벽에 대해 한 번씩 부수고, 탐색을 하다가 근처에 이동할 수 있는 길이 없다면 반복을 종료하고, 다시 벽을 세우면서 돌아오는 백트레킹 방식을 구현했다. 나름 잘 짰다고 생각하며 뿌듯해하며 제출을 했지만 시간초과가 났다..ㅜ
• 도대체 어떻게 해야 시간을 줄일 수 있을까 고민을 하다가 구글링을 통해 다른 방식을 사용했는데, 이러한 유형도 자주 출제 된다고 하니 코드를 이해하고 암기하기로 했다. 참고한 사이트는 여기를 눌러주길 바란다.
• 항상 보면 조건을 나눌 때 경우의수를 판단하지 않고 그저 경험에 따라 습관적으로 if문을 쓰는 것 같은데, 조건에 대해서도 한 번 생각해보고 그에 따라 경우의 수를 나누어 명령을 처리하는 연습을 해야 겠다.

 [ 풀이 ]

• 사용자 정의 객체를 만들어서 객체의 멤버 변수로는 좌표값 x,y 벽을 부셨는지 여부(boolean), 현재 이동거리(1부터시작)를 선언하고 이에 따른 생성자를 만들어 준다. 
• 반복에서 검사하는 조건은 다음과 같다. 
  • 맵의 범위를 벗어나지 않는 경우 중에서 ~ 
    • 벽이 아니라 이동할 수 있는 길이라면(값이 0이라면)
      • 아직 벽을 부순 적이 없고, 방문한 적이 없다면 ~ 
        • 방문체크 : visit[x][y][0] = true; (같은 좌표에 대해 벽을 부셨다면 [0], 아니라면 [1]에 방문체크)
        • Enqueue : q.add(new bricks(x, y, false, now.dist+1))
      • 벽을 한 번 부순 적이 있고, 방문한 적이 없다면 ~ 
        • 방문체크 : visit[x][y][1] = true; (같은 좌표에 대해 벽을 부셨다면 [0], 아니라면 [1]에 방문체크)
        • Enqueue : q.add(new bricks(x, y, true, now.dist+1))
    • 이동할 수 없는 벽이라면 (값이 1이라면) {벽은 애초에 방문할 수 없으니 부쉈는지 안부쉈는지만 체크}
      • 아직 벽을 부순 적이 없다면 ~
        • 방문체크 : visit[x][y][1] = true; (같은 좌표에 대해 벽을 부셨다면 [0], 아니라면 [1]에 방문체크)
        • Enqueue : q.add(new bricks(x, y, true, now.dist+1))
      • 벽을 부순 적이 있다면, 벽은 최대 한 번만 부술 수 있기 때문에 Skip

 

[ 소스코드 ]

package BFS;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class bricks{
    int x; 
    int y;
    boolean isBroken;
    int dist;
    
    public bricks() {
        super();
    }
 
    public bricks(int x, int y, boolean isBroken, int dist) {
        super();
        this.x = x;
        this.y = y;
        this.isBroken = isBroken;
        this.dist = dist;
    }
}
 
public class _2206_벽뚫기 {
    static int n, m;
    static int map[][];
    static boolean visit[][][];
    static int dx[] = { -1, 1, 0, 0 };
    static int dy[] = { 0, 0, -1, 1 };
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        map = new int[n][m];
        
        //벽을 부쉈는지를 확인할 3중배열
        visit = new boolean[n][m][2];
        
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = str.charAt(j) - '0';
                
            }
        }
        
        
        
        BFS(0, 0);
        
    }
 
    private static void BFS(int x, int y) {
        // TODO Auto-generated method stub
        Queue<bricks> q = new LinkedList<bricks>();
 
        //초기위치는 0이 보장되어 있다. 방문체크 + 부심 여부
        visit[x][y][0] = false;
        q.add(new bricks(x, y, false, 1));
 
        while (!q.isEmpty()) {
            bricks now = q.poll();
            
            if(now.x == n-1 && now.y == m-1) {
                System.out.println(now.dist);
                return;
            }
 
            for (int i = 0; i < 4; i++) {
                int xx = now.x + dx[i];
                int yy = now.y + dy[i];
                
                if (xx >= 0 && yy >= 0 && xx < n && yy < m) {
                    
                    if(map[xx][yy]== 0) {//벽이 아니면
                        //아직 부신벽이 없다면 
                        if(!now.isBroken && !visit[xx][yy][0]) {
                            visit[xx][yy][0] = true;
                            q.add(new bricks(xx, yy, false, now.dist+1));
                        }else if(now.isBroken && !visit[xx][yy][1]) {//벽을 한 번 부신 적이 있다면
                            visit[xx][yy][1] = true;
                            q.add(new bricks(xx, yy, true, now.dist+1));
                        }
                    }else if (map[xx][yy] == 1) {//벽이면
                        if(!now.isBroken) {//한 번도 부순 적이 없다면 부숴라
                            visit[xx][yy][1] = true;
                            q.add(new bricks(xx, yy, true, now.dist+1));
                        }
                    }
                }
            }
        }//end-while
        
        System.out.println(-1);
    }
 
}