미로 탐색

조소복·2022년 9월 6일

문제

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

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

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

입력

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

출력

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

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

예제 입력 4

예제 출력 4

문제 풀이

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int result=Integer.MAX_VALUE;
    static int[][] moves={{0,1},{0,-1},{1,0},{-1,0}};
    static int[][] map;
    static int[][] visited;

    public static class Point{
        int x,y;
        int dis;

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

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

        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());

        map=new int[N][M];
        visited=new int[N][M];

        for(int i=0;i<N;i++){
            String[] tmp=br.readLine().split("");
            for(int j=0;j<M;j++){
                map[i][j]=Integer.parseInt(tmp[j]);
            }
        }

        bfs(N,M);

        System.out.println(visited[N-1][M-1]);
    }

    public static void bfs(int N,int M){
        Queue<Point> queue=new ArrayDeque<>();
        queue.add(new Point(0,0,1));

        while(!queue.isEmpty()){
            Point p=queue.poll();
            for(int i=0;i<4;i++){
                int a=p.x+moves[i][0];
                int b=p.y+moves[i][1];
                if(a<0 || a>=N || b<0 || b>=M) continue;

                if(visited[a][b]==0 && map[a][b]==1){
                    visited[a][b]=p.dis+1;
                    queue.add(new Point(a,b,p.dis+1));
                }
            }
        }

    }
}

미로의 길이 있어야하고 출발점으로부터 몇번째 거쳤는지 체크하면 답을 구할 수 있다.

BFS를 이용해서 지나온 길을 체크하고 해당 위치에 출발점으로부터 거리값을 저장해준다.

Queue에 넣을 값

public static class Point{
    int x,y;
    int dis;

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

x좌표, y좌표와 지나온 거리값 변수를 만들어준다.

bfs를 통한 길 체크

public static void bfs(int N,int M){
    Queue<Point> queue=new ArrayDeque<>();
    queue.add(new Point(0,0,1));

    while(!queue.isEmpty()){
        Point p=queue.poll();
        for(int i=0;i<4;i++){
            int a=p.x+moves[i][0];
            int b=p.y+moves[i][1];
            if(a<0 || a>=N || b<0 || b>=M) continue;

            if(visited[a][b]==0 && map[a][b]==1){
                visited[a][b]=p.dis+1;
                queue.add(new Point(a,b,p.dis+1));
            }
        }
    }
}