[JAVA] 백준 2178번 - 미로 탐색

문제

입력

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

출력

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

구현 방법

문제를 읽어보면 알 수 있듯이 최단거리를 구하는 문제이다. BFS를 사용하여 문제를 풀면 된다. 배열로 된 미로이니 2차원 배열과 큐를 사용하겠다. 전체코드는 가장 아래!

1. 입력값을 받아서 저장 -> 이를 가지고 2차원 배열에 위치를 저장
2. BFS함수 호출
3. BFS함수 구현
   • 큐 생성 -> 큐에 {x, y, 거리} 배열 삽입
   • while문 : 상하좌우 4방향 확인하며 x,y찾기 -> 갈 수 있는 위치라면 이동 후 다음 위치 거리 삽입

전체 코드

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

public class Main {
    static int N, M;
    static int[][] arr; //위치 2차원 배열
    static boolean[][] visited; //방문확인
    static int distance; //거리
    static int[] dx = {1,0,-1,0}; //우부터 반시계
    static int[] dy = {0,1,0,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        //초기화
        arr = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

        //위치 저장
        for(int i=1; i<=N; i++) {
            String str = br.readLine();
            char[] c = str.toCharArray(); //1개씩 잘라 배열
            for(int j=1; j<=M; j++)
                arr[i][j] = Character.getNumericValue(c[j-1]);
        }
        BFS(1,1);
    }
    public static void BFS(int x, int y) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{x,y,1}); //x,y,거리 삽입
        visited[x][y] = true;

        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentX = current[0];
            int currentY = current[1];
            distance = current[2];

            if(currentX==N && currentY==M) break; // 목적지 도달 종료
            //최단 경로 찾기(거리)
            for(int i=0; i<4; i++) {
                int nx = currentX + dx[i];
                int ny = currentY + dy[i];

                if(nx>=1 && ny>=1 && nx<=N && ny<=M && arr[nx][ny]==1 && !visited[nx][ny]) {//배열범위, 이동가능, 방문X
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx,ny,distance+1}); //다음 위치 거리 삽입
                }
            }
        }
        System.out.println(distance);
    }
}

=> 구현 방법과 코드에 달린 주석을 보면서 차근차근 해보면 충분히 할 수 있다!!👏👏👏