백준 2178번 : 미로 탐색 (JAVA) 문제 풀이

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

2178번: 미로 탐색

---

 

✏️ 문제

 

 

🔐 문제 해결

이 문제는 이전의 풀었던, 그림 문제처럼 풀면 안된다. 이전 문제처럼 풀게 되면 최단거리를 구하지 못한다.

그래서 이 문제는 시작지점(0,0)으로 부터의 모든 칸의 거리를 계산하여 또 다른 배열에 저장을 할 것이다.

이게 무슨 말이냐면, 아래 그림을 보면

우리가 구해야 하는 경로는 빨간색 경로인데, 어떻게 구하냐면 위에서 말했듯이 시작점으로부터의 거리를 계산한 배열을 생성해줄것이다.

int[][] dist = new int[N][M];	// 시작점과의 거리를 저장하는 2차원 배열

 

이제 시작점에서 부터 출발하여 1인 경로를 따라가면서 거리를 계산하여 dist배열에 넣어주기만 하면 된다!

시작점을 (0,0) 으로 미리 큐에 넣어준 상태에서 상하좌우의 값이 1인지 아닌지 체크하면 된다.

거리 계산을 할 때에는, 이전 시작점의 + 1 만 해주면 된다. 아래 코드를 살펴보자.

qu.offer(new Pair(0,0));  // 시작점
dist[0][0] = 0;   // 첫 시작이니까 거리가 0이다.
   
while(!qu.isEmpty()){
    Pair p = qu.poll();
    
    // 상, 하, 좌, 우를 계산해준다.
    for(int i=0; i<4; i++){
      int nX = p.x + dx[i];
      int nY = p.y + dy[i];
      
      // 벽에 부딪히거나, 범위를 넘어가면 PASS
      if(nX < 0 || nX >= N || nY < 0 || nY >= M){
          continue;
      }
      // 길이 아니거나, 방문을 했다면 PASS
      if(miro[nX][nY] == '0' || dist[nX][nY] != -1){
          continue;
      }
      
      // 큐에 이동한 좌표를 넣어준다.
      qu.offer(new Pair(nX, nY));
      // 한칸 이동하였기 때문에, 이전 출발지점의 거리 +1을 해준다.
      dist[nX][nY] = dist[p.x][p.y] + 1;
    }
}

저 경로를 하나하나 계산해주면 아래의 그림처럼 나오게 된다.

여기서 의문점이 드는 점은 최장경로일 때의 15가 저장이 될 수도 있는거 아닌가? 라고 생각할 수 있는데, 큐에서 서로의 경로를 하나씩 넣고 빼고 하기 때문에 결국엔 가장 빠른 경로가 먼저 도달하여 배열에 값을 넣게 된다. 그렇게 되기 때문에 오래 걸린 경로는 배열에 값을 넣으려고 해도 이미 값이 있기 때문에 값을 넣지 못하게 되는 것이다! 아래 조건처럼 말이다.

// 거리 계산하는 배열(dist)을 -1로 값을 세팅 해둘 것이기 때문에 이미 값이 있다면 PASS!
if( miro[i][j] == 0 || dist[i][j] != -1 ){
	continue;
}

 

🖥 전체 코드

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

public class Main {
    public static void main(String args[]) throws IOException {
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(bf.readLine());
      
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      char[][] miro = new char[N][M];  // 미로를 저장할 배열
      int[][] dist = new int[N][M];    // 거리를 계산할 dist 배열
      int[] dx = {1, 0 , -1, 0};       // 상하좌우 계산할 x좌표
      int[] dy = {0, 1, 0, -1};        // 상하좌우 계산할 y좌표
      Queue<Pair> qu = new LinkedList<>();
      
      for(int i=0; i<N; i++){
          String line = bf.readLine();
          for(int j=0; j<M; j++){
              miro[i][j] = line.charAt(j);
              dist[i][j] = -1;    // 거리를 -1로 세팅하면, 방문여부를 확인가능.
          }
      }
      
      qu.offer(new Pair(0,0));  // 시작점
      dist[0][0] = 0;   // 첫 시작이니까 거리가 0이다.
      
      while(!qu.isEmpty()){
          Pair p = qu.poll();
          
          // 상, 하, 좌, 우를 계산해준다.
          for(int i=0; i<4; i++){
            int nX = p.x + dx[i];
            int nY = p.y + dy[i];
            
            // 벽에 부딪히거나, 범위를 넘어가면 PASS
            if(nX < 0 || nX >= N || nY < 0 || nY >= M){
                continue;
            }
            // 길이 아니거나, 방문을 했다면 PASS
            if(miro[nX][nY] == '0' || dist[nX][nY] != -1){
                continue;
            }
            
            // 큐에 이동한 좌표를 넣어준다.
            qu.offer(new Pair(nX, nY));
            // 한칸 이동하였기 때문에, 이전 출발지점의 거리 +1을 해준다.
            dist[nX][nY] = dist[p.x][p.y] + 1;
          }
      }
      
      // 마지막 지점의 (거리 + 1)를 출력해주면 된다.
      System.out.print(dist[N-1][M-1] + 1);
    }
    
    // 큐에 좌표를 넣어주기 위한 클래스
    public static class Pair{
        int x, y;
        
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        public int getX(){
            return x;
        }
        public int getY(){
            return y;
        }
        public void setX(int x){
            this.x = x;
        }
        public void setY(int y){
            this.y = y;
        }
    }
}