[java]벽 부수고 이동하기 - 백준2206

문제

• 벽 부수고 이동하기(백준2206)

풀이

문제 해석을 하자면,

• (1,1) -> (N,M) 좌표로 이동하는 최단 거리를 구하는 문제이다.
• 벽을 1번까지 부수고 지나갈 수 있다는 조건을 해결하는게 핵심이다.

풀이

• 이 문제의 경우 코드 구현은 금방했는데, 해당 아이디어를 생각하는게 좀 오래걸렸다. (기본이 부족 ㅜㅜ)
• 우선 가중치가 동일하므로 다익스트라가 아닌 BFS로 충분히 해결 가능하다.
• 그리고 BFS의 특성을 잘 생각해보면 풀이를 떠올리기 쉽다.
  • BFS로 조회하면 해당 레벨에 첫 조회했을때 무조건 최단거리!!
  • 즉, 무엇이든 처음 방문이 최단경로(BFS특성)
• 따라서 visited 2개를 사용!! -> 벽O, 벽X 의 경우로 나눈것
  • 벽을 부순상태의 경로들을 따로 방문 처리 함으로써 “중복방문 방지”
  • 벽을 부수지않은 상태의 경로들을 따로 방문 처리 함으로써 “중복방문 방지”
  • 참고) BFS로 조회하는데 “중복방문 방지”는 꼭 고려해줘야 무한처리를 방지!
• 마지막으로 거리는 트리 레벨을 활용!! -> 이것이 “최단거리”가 되는건 자명하다.

코드

import java.io.*;
import java.util.*;

/**
 * (1, 1)과 (N, M)은 항상 0 -> 본인은 (0,0)부터 사용하겠다.
 * 풀이 : 최단경로 -> 가중치동일 -> BFS
 * visited 2개와 트리레벨 활용해보자 -> visited 2개 사용이 핵심!!
 * +따로 wall 변수에 벽을 부수었는지 기록해서 사용
 * +visited 2개는 벽O, 벽X 의 경우로 나눈것 -> 무엇이든 처음 방문이 최단경로(BFS특성)
 * 참고) N==1 && M==1 일 때 벽아니면 이것도 한칸이므로 level 1로 봐야함. (본인 코드는 level 2로 나오게 짜서 따로 예외처리 함)
 */
public class Main {

  public static int N,M;
  public static int[][] inArr = new int[1005][1005];
  public static boolean[][] visitedNoWall = new boolean[1005][1005];
  public static boolean[][] visitedYesWall = new boolean[1005][1005];
  public static int result1 = Integer.MAX_VALUE;
  public static int result2 = Integer.MAX_VALUE;
  public static int[] dx = {0,1,0,-1};
  public static int[] dy = {1,0,-1,0};

  public static void bfs() {
    Queue<Pair> qu = new ArrayDeque<>();
    qu.offer(new Pair(0,0, 0));
    visitedNoWall[0][0] = true;
    int level = 1; // (0,0) 부터시작
    if(N==1&&M==1) level=0; // 아래에서 어차피 ++하기 때문에 예외처리
    while(!qu.isEmpty()) {
      //debug
//      System.out.println(Arrays.toString(qu.toArray()));
//      System.out.println("level:"+level);
      int size = qu.size();
      level++;
      for(int s=0; s<size; s++){
        Pair p=qu.poll();
        //debug
//        if(p.x == 4 && p.y==0) {
//          System.out.println("debug");
//        }
        for(int i=0; i<4; i++){
          int nx = p.x + dx[i];
          int ny = p.y + dy[i];
          if(nx<0||ny<0||nx>=N||ny>=M) continue;
          if(p.wall==0) { // 아직 벽 안부순경우
            if(inArr[nx][ny] == 0) {
              if(visitedNoWall[nx][ny]) continue;
              qu.offer(new Pair(nx, ny, 0)); // 큐 삽입시점
              visitedNoWall[nx][ny]=true;
            }else {
              if(visitedYesWall[nx][ny]) continue;
              qu.offer(new Pair(nx, ny, 1)); // 큐 삽입시점
              visitedYesWall[nx][ny]=true;
            }
          }else { // 이미 벽 부순경우
            if(inArr[nx][ny] == 0) {
              if(visitedYesWall[nx][ny]) continue;
              qu.offer(new Pair(nx, ny, 1)); // 큐 삽입시점
              visitedYesWall[nx][ny]=true;
            }else {
              continue; // 이미 벽도 부쉈고(wall=1), 맵에 벽을 만난경우(inArr[nx][ny]=1)
            }
          }
        }
      }
      // 기록 -> 종료시점
      if(visitedNoWall[N-1][M-1]) {
        result1 = level; break;
      }
      if(visitedYesWall[N-1][M-1]) {
        result2 = level; break;
      }
    }

    //최종 출력
    if(visitedNoWall[N-1][M-1] || visitedYesWall[N-1][M-1]){
      System.out.println(Math.min(result1,result2));
    }else{
      System.out.println(-1);
    }

  }

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    for(int i=0; i<N; i++){
      String inStr = br.readLine();
      for(int j=0; j<M; j++){
        inArr[i][j] = inStr.charAt(j)-'0'; // 숫자로 입력
      }
    }
    //run
    bfs();

  }
  static class Pair {
    int x; int y; int wall;
    public Pair(int x, int y, int wall) {
      this.x=x; this.y=y; this.wall=wall;
    }

    @Override
    public String toString() {
      return "x:"+x+" y:"+y+" wall:"+wall;
    }
  }
}

느낀점

debug를 잘 찍는것도 좋은 습관이다!