[BOJ/JAVA] 백준 2178 : 미로 탐색 (자바)

문제 정보

  문제명   - 미로 탐색
  난이도   - 실버 I
문제 번호 - 2178번

---

문제 링크

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

2178번: 미로 탐색

---

문제

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

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

---

입력

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

---

출력

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

---

예제 입력/출력

예제 입력	예제 출력
4 6 101111 101010 101011 111011	15​
4 6 110110 110110 111111 111101	9​
2 25 1011101110111011101110111 1110111011101110111011101	38
7 7 1011111 1110001 1000001 1000001 1000001 1000001 1111111	13​

---

알고리즘 분류

● 그래프 이론
● 그래프 탐색
● 너비 우선 탐색

---

소스코드

package Lv2_Silver;

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

/**
 * @author HanHoon
 * @category 그래프 이론, 그래프 탐색, 너비 우선 탐색
 * https://www.acmicpc.net/problem/2178
 */
public class BOJ_S1_2178_미로_탐색 {
    static int N, M;
    static int[][] map;
    static boolean[][] isVisited;
    public static void bfs(){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {0,0});
        isVisited[0][0] = true;

        // 상하좌우
        int[] dCol = {-1, 1, 0, 0};
        int[] dRow = { 0, 0,-1, 1};

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

            // 상하좌우
            for(int i = 0; i < 4; i++){
                int nextY = currentY + dCol[i];
                int nextX = currentX + dRow[i];

                // 범위 체크
                if(nextY >= N || nextY < 0 || nextX >= M || nextX < 0)
                    continue;
                // 간던 곳인지, 길인지 체크
                if(isVisited[nextY][nextX] || map[nextY][nextX] == 0)
                    continue;

                queue.offer(new int[] {nextY, nextX});
                map[nextY][nextX] = map[currentY][currentX] + 1;
                isVisited[nextY][nextX] = true;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder str = new StringBuilder();

        // N
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        isVisited = new boolean[N][M];

        for (int n = 0; n < N; n++){
            String s = br.readLine();
            for(int m = 0; m < M; m++)
                map[n][m] = s.charAt(m) - '0';
        }

        bfs();

        str.append(map[N-1][M-1]);

        System.out.print(str);
        br.close();
    }
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---