[Java] 백준 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)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    static int[][] graph = new int[100][100];
    static boolean[][] visited = new boolean[100][100];
    static int n = 0;
    static int m = 0;
    static int len[] = { 0, 0, 1, -1 };
    static int wid[] = { 1, -1, 0, 0 };
 
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        m = input.nextInt();
 
        String nString = "";
        for (int i = 0; i < n; i++) {
            nString = input.next();
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(nString.charAt(j) + "");
            }
        }
 
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                visited[i][j] = false;
            }
        }
 
        find();
    }
 
    private static void find() {
 
        int roadCount = 0;
        int qSize;
        int temp;
        int r;
        int c;
        int finish = 0;
 
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(0);
 
        while (finish != 1) {
            qSize = q.size();
 
            for (int i = 0; i < qSize; i++) {
                temp = q.poll();
                r = temp / 100;
                c = temp % 100;
 
                if (r == n - 1 && c == m - 1) {
                    roadCount++;
                    System.out.println(roadCount);
                    finish = 1;
                }
 
                for (int j = 0; j < 4; j++) {
                    int nr = r + wid[j];
                    int nc = c + len[j];
 
                    if (nr >= n || nr < 0 || nc >= m || nc < 0)
                        continue;
 
                    if (graph[nr][nc] == 0)
                        continue;
 
                    if (visited[nr][nc])
                        continue;
 
                    visited[nr][nc] = true;
                    q.offer(nr * 100 + nc);
                }
            }
            roadCount++;
        }
    }
}