백준 2178) 미로탐색 자바 Java

문제

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

 

 

풀이

풀이의 핵심은 "최단경로"이다. bfs를 사용하여 풀었고, 이동하는 위치(1이 적힌)값을 이전의 거리 값 + 1을 하며 업데이트하며 목적지까지 이동하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


class Point {
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static StringTokenizer st;
    static int N,M,count;
    static Queue<Point> q;
    static int[][] arr;
    static boolean[][] visited;

    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static String[] line ;
    public static int bfs(int x, int y){
        q = new LinkedList<>();
        Point cp = new Point(x,y);
        q.offer(cp);
        visited[x][y] = true;
        while(!q.isEmpty()){
            Point p = q.poll();
            for (int i = 0 ; i < 4; i ++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny <M && visited[nx][ny] == false && arr[nx][ny] == 1){
                    visited[nx][ny] = true;
                    q.offer(new Point(nx,ny));
                    arr[nx][ny] = arr[p.x][p.y] + 1;
                }
            }
        }
        return arr[N-1][M-1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 x = 0 ; x < N; x++){
            line = br.readLine().split("");
            for (int y = 0 ; y < M; y++){
                arr[x][y] = Integer.parseInt(line[y]);
            }
        }

        System.out.println(bfs(0,0));

    }
}