[알고리즘] 백준_미로 탐색 - 2178

문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

문제 분석 및 해결 방법

N, M의 초대 데이터의 크기가 100으로 작기 때문에 시간 제한을 신경 쓰지 않아도 된다. DFS와 BFS를 사용할 수 있지만, BFS를 사용하면 최초로 도달했을 때 깊이를 출력하면 된다.

우선 2차원 배열에 데이터를 저장해주고 처음 위치에서 BFS를 시작해주면 된다. BFS는 처음에는 파라미터로 받은 값을 큐에 넣어주고, now배열로 현재 위치를 저장하고, dx, dy 배열을 사용해서 상, 하, 좌, 우를 탐색해준다. 조건이 맞으면 방문 기록을 해주고 다음 위치에 깊이를 업데이트해준다. 그 후 큐에 새로운 위치를 추가해준 후 큐가 빌 때까지 반복해준다.

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

public class Main {
    static int N,M;
    static int[] dx = {-1,1,0,0}; // 상하
    static int [] dy = {0,0,-1,1}; // 좌우
    static boolean[][] visited;
    static int [][] arr;
    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 = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0;i<N;i++){
            String s = br.readLine();
            for(int j=0;j<M;j++){
                arr[i][j] = s.charAt(j)-'0';
            }
        }
        BFS(0,0);
        bw.write(Integer.toString(arr[N-1][M-1]));
        bw.close();
    }
    private static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(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(arr[x][y]!=0 && !visited[x][y]) {
                        visited[x][y] = true;
                        arr[x][y] = arr[now[0]][now[1]]+1; // 현재 위치에서 깊이 업데이트
                        queue.add(new int[]{x,y}); // 새로운 위치를 추가
                    }
                }
            }
        }
    }
}

참고 : Do it! 알고리즘 코딩테스트 with JAVA