[BOJ] 2178 - 미로 탐색

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/2178

2178번: 미로 탐색

난이도: 실버 1

사용 언어: JAVA

 

아래의 그림과 같이 NxM 배열로 표현되는 미로에서 1은 이동할 수 있는 칸을, 0은 이동할 수 없는 칸을 나타냅니다. 이때 가장 좌측 상단에서 출발하여, 가장 우측 하단까지 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제입니다.

 

위의 예시에서는 최소 15칸을 지나야 가장 우측 하단에 닿을 수 있습니다. 칸을 셀 때는 시작 위치와 도착 위치도 포함합니다.

 

풀이

이 문제는 BFS를 이용하면 어렵지 않게 해결할 수 있는 문제이며, 저는 큐를 이용하여 BFS를 구현했습니다. 우선 2차원 배열에 해당 미로를 담아줍니다. 그리고 가장 좌측 상단의 좌표를 큐에 넣어줍니다. 

 

반복문을 돌며 BFS를 수행하게 되는데, 한 번 반복문이 돌 때마다, 현재 큐에 있는 요소들을 하나씩 다 꺼내어 해당 칸의 인접 칸들을 조사합니다. 인접 칸이란, 해당 칸의 상하좌우에 있는 칸을 뜻합니다. 인접 칸이 1일 경우에만, 다시 조사되는 일을 막기 위해 그 칸을 0으로 만들어 준 뒤, 큐에 넣어줍니다. 

 

반복문이 한 번 실행될 때마다 한 칸씩 퍼져 나갈 수 있으므로, 최종적으로 가장 우측 하단의 칸이 큐에 들어갈 때, 반복문을 멈추고 반복문을 몇 번 돌았는지를 출력해주면 됩니다. 아래의 그림을 통해 다른 예시에 대한 단계를 따라가 보도록 하겠습니다.

 

진한 색으로 표시된 부분들이 현 시점에 큐에 들어가 있는 부분들이고, 연하게 표시된 부분들이 이미 큐에 들어갔다가 나온 부분들입니다.

 

마지막 그림까지 반복문을 수행하면, 가장 우측 하단의 칸이 큐에 들어가게 됩니다. 그렇게 되면 몇 차례 반복문을 돌았는지를 출력해주고, 프로그램을 종료시킵니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class position{ // 큐에 칸의 위치를 넣기위해 좌표를 표현할 클래스 생성
    int x;
    int y;
}
 
class Main {
    static Queue<position> q = new LinkedList<position>(); // 큐를 이용해 BFS 구현
    static int N, M;
    static int cnt = 1; // 첫 칸을 큐에 넣은 채로 시작하기 때문에 1부터 카운트
 
    public static void bfs(int x, int y, char arr[][]){
 
        if(x-1 >=0 && arr[x-1][y] == '1'){ // 윗 칸이 1이라면?
            position p = new position();
            arr[x-1][y] = '0'; // 해당 칸을 0으로 만들어주고,
            p.x = x-1;
            p.y = y;
            q.add(p); // 큐에 집어준다.
        }
        if(y+1 < M && arr[x][y+1] == '1'){ // 오른쪽 칸이 1이라면?
            position p = new position();
            arr[x][y+1] = '0';
            p.x = x;
            p.y = y+1;
            q.add(p);
        }
        if(x+1 < N && arr[x+1][y] == '1'){ // 아래 칸이 1이라면?
            position p = new position();
            arr[x+1][y] = '0';
            p.x = x+1;
            p.y = y;
            q.add(p);
        }
        if(y-1 >=0 && arr[x][y-1] == '1'){ // 왼쪽 칸이 1이라면?
            position p = new position();
            arr[x][y-1] = '0';
            p.x = x;
            p.y = y-1;
            q.add(p);
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        char [][]arr = new char[N][M];
        int i, j;
 
        for(i=0;i<N;i++){ // 2차원 배열에 미로를 넣어준다.
            s = br.readLine();
            for(j=0;j<M;j++){
                arr[i][j] = s.charAt(j);
            }
        }
 
        position p = new position();
        p.x = 0;
        p.y = 0;
        q.add(p); // 시작 지점은 (0,0)
        arr[0][0] = '0';
        while(true) {
            int k = q.size(); // 현 시점에 큐에 들어있는 만큼
            for(i=0;i<k;i++) { // 다 꺼내서 BFS 수행
                p = q.remove();
                if(p.x == N-1 && p.y == M-1) { // 가장 우측 하단에 도착하면 종료
                    System.out.println(cnt);
                    System.exit(0);
                }
                bfs(p.x, p.y, arr);
            }
            cnt++; // 반복문을 한 번 돌 때마다 카운트 증가
        }
    }
}