탐색 알고리즘 문제 풀어보기 3(백준 2178번 미로 탐색하기)

이번 문제는 미로가 주어지면 출구까지의 최단거리를 찾는 문제이다.

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

2178번: 미로 탐색

미로는 2차원배열형대로 주어지고 무조건 답이 있다. 처음에는 갈 수 있는 길을 쭉 찾아나가며 DFS로 해결하려 했지만 메모리 초과가 나왔다. 이 문제에서 DFS는 모든 경우의 수를 탐색해 가장 작은 정답을 골라야 하는데 탐색하며 가짓수가 너무 많이 생기면 재귀함수가 너무 많이 호출되어 메모리가 초과되는 문제가 발생하였다. 따라서 이 문제는 DFS로는 불가능하고 BFS를 이용해야 한다. 핵심은 BFS로 현재 진행 횟수에서 갈 수 있는 모든 위치를 표시하다가 출구가 나오는 즉시 멈추고 현재 진행 횟수를 출력하는 것이다. 이러면 모든 경우의 수에 대해 끝까지 탐색을 하지 않아도 되므로 시간과 메모리에서 많은 이점이 있다. 다음은 작성한 코드이다.

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

public class Main {
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    static boolean[][] visited;
    static int[][] map;
    static int N;
    static int M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
        for(int i=0;i<N;i++){
            String a = br.readLine();
            for(int j=0;j<M;j++){
                map[i][j] = Integer.parseInt(a.substring(j,j+1));
            }
        }
        miro(0,0);
        bw.write(map[N-1][M-1]+"");
        bw.flush();
        bw.close();
    }
    static void miro(int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i,j});
        visited[i][j] = true;
        while(!queue.isEmpty()){
            int now[] = queue.poll();
            for(int k=0;k<4;k++){
                int x = now[0]+dx[k];
                int y = now[1]+dy[k];
                if(x>=0 && y>=0 && x<N && y<M){
                    if(map[x][y]!=0 && !visited[x][y]){
                        visited[x][y] = true;
                        map[x][y] = map[now[0]][now[1]]+1;
                        if(x==N-1 && y==M-1) return;
                        queue.add(new int[] {x,y});
                    }
                }
            }
        }
    }
}

현재 위치에서 상하좌우를 탐색할 때 배열의 범위 밖으로 나가 인덱스오류가 생기지 않도록 처리해주어야 한다. 탐색은 if구문으로 4번 반복하는 방법도 있지만 미리 배열을 2개 만들어 반복문으로 하는 방법이 더 깔끔한 것 같다. 이미 탐색한 곳으로 되돌아가는 행동을 방지하기 위해 방문했던 위치를 기록해 비교하면서 탐색해야 한다. 탐색을 하다가 출구의 위치에 도착하면 바로 함수를 종료하고 결과를 출력한다.

이번 문제는 지난번과는 반대로 DFS로는 풀 수 없고 BFS로만 풀 수 있는 문제였다. 문제를 처음 보고 어떻게 풀지 설계를 할 때 가장 효율적인 방법을 택해야 빠르고 정확하게 문제를 해결할 수 있을 것 같다.