[BOJ] 2206 벽 부수고 이동하기 - JAVA

1. 문제

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

벽을 왜부숴 길이 없으면 다시 돌아가

---

2. 풀이

입력 및 BFS탐색에 필요한 변수와 객체들

거리 저장은 꼭! 3차원이어야 한다. 벽을 한번 부수고 왔을 때/부수지 않았을 때 두 가지 경우가 필요하기 때문이다. 이렇게 굳이 나누는 이유는 아래에서 서술한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] deltas = {{1,0},{0,1},{0,-1},{-1,0}};

char[][] map = new char[N][M];
for(int i=0;i<N;i++) map[i] = in.readLine().toCharArray();
int[][][] dist = new int[2][N][M];

 

BFS 탐색 - 3차원ver.

1.  큐에 들어갈 객체는 3칸짜리 배열이다. n, m, 벽을 부쉈는지 여부를 저장한다.

2. dist[벽을 부쉈다면 1, 부수지 않았다면 [0][n][m]

3.  처음에는 벽을 부수지 않았으므로 depth[0][0][0]에 1을 저장한다.(문제에서 1부터 시작한다고 했다.)

4.  이제 new int[]{0,0,0}를 큐에 넣고 탐색을 시작한다.

5.  큐에 다음 방문장소를 넣지 "않는" 경우는 다음과 같다.

• 범위에서 벗어났을 때
• 다음 방문장소가 벽(1)인데 이미 이전에 한번 벽을 부순 적(w == 1)이 있을 때
• dist[다음방문장소]에 이미 저장된 값이 있을 때(!= 0)

6.  dist가 3차원 배열인 이유도 여기에 있다. 2차원 배열이라고 생각해보자. 같은 장소에 여러 번 도달했다고 했을 때, 이미 저장된 dist와 지금 저장할 dist(직전 dist+1)와 단순비교는 할 수 있지만 저장되었던 값이 벽을 부수고 온 상태인지, 벽을 한번도 부수지 않은 상태인지 알 수 없다. 그래서 저장된 값이 있으면 바로 continue 시키는 지금과 다르게 하나하나 다 비교해주어야 한다. (=> 메모리초과, 시간초과가 난다.) 그리고 애초에 두 경우가 섞여서 정상적인 값이 나오지 않는다.

Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0,0,0});
dist[0][0][0] = 1;
int w,n,m,l,nn,nm;

while(!queue.isEmpty()){
   w = queue.peek()[0];//벽 부쉈는지
   n = queue.peek()[1];
   m = queue.poll()[2];
   l = dist[w][n][m];//경로길이

   for(int[] d:deltas){
      nn = n+d[0];
      nm = m+d[1];
      if(nn<0 || nn>=N || nm<0 || nm >= M) continue;
      if(map[nn][nm]=='1' && w==0 && dist[1][nn][nm] == 0){
         queue.offer(new int[]{1,nn,nm});
         dist[1][nn][nm] = l+1;
      }else if(map[nn][nm]=='0' && dist[w][nn][nm] == 0){
         queue.offer(new int[]{w,nn,nm});
         dist[w][nn][nm] = l+1;
      }
   }
}

 

출력

0인 경우는 도달하지 못한 경우이기 때문에 조건을 다 나눠줘야 한다.

if(dist[0][N-1][M-1] == 0 && dist[1][N-1][M-1] == 0) System.out.println(-1);
else if(dist[0][N-1][M-1] == 0) System.out.println(dist[1][N-1][M-1]);
else if(dist[1][N-1][M-1] == 0) System.out.println(dist[0][N-1][M-1]);
else System.out.println(Math.min(dist[0][N-1][M-1],dist[1][N-1][M-1]));

---

3. 결과

3차원배열까지 써볼 생각을 못했다. 큐에만 벽을 부순 상태를 저장하면 되는 줄 알았는데 그게 아니었다. ㅠㅠ BFS는 방문할 수 있는 경우라면 가장 최소거리로 방문하므로 각 상태마다 최소가 다른 경우는 나눠주어야 했다.

일년 후 ... 좀 더 나아졌다 ^_^ (본문 코드는 오늘 코드다)