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

입력

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

출력

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

예제 입력 1 복사

4 6
101111
101010
101011
111011

예제 출력 1 복사

15

예제 입력 2 복사

4 6
110110
110110
111111
111101

예제 출력 2 복사

9

예제 입력 3 복사

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 복사

38

예제 입력 4 복사

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4 복사

13

 

• 풀이 

BFS로 최소 이동 횟수를 계산 가능하다
dist 배열을 만들어서 nx,ny의 dist는 이전 x,y의 dist +1을 저장하는 방법으로 최소 이동 횟수, 최단 시간 등을 구할 수 있다
!가중치 없는 경우에 사용 가능하다

bfs(x,y)를 해놓고 밑에 dist 계산에 dist[nx][ny] = dist[x][y]+1; 를 해둬서 값이 2에서 늘어나지 않는 실수를 찾느라 

시간을 많이 썻다.. 

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

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

public class Main {

    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    static String s; static StringTokenizer st;
    static int N, M;
    static int[][] dist;
    static boolean[][] isVisited;
    static Node[][] arr;
    static void bfs(int x, int y){

        Queue<Node> queue = new LinkedList<>();
        queue.add(arr[x][y]);
        isVisited[x][y] = true;
        dist[x][y] = 1;

        while (!queue.isEmpty()){
            Node tmp = queue.poll();

            for (int i = 0; i < 4; i++){
                int nx = tmp.x + dir[i][0];
                int ny = tmp.y + dir[i][1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (isVisited[nx][ny]) continue;
                if (arr[nx][ny].gap == 1){
                    queue.add(arr[nx][ny]);
                    isVisited[nx][ny] = true;
                    dist[nx][ny] = dist[tmp.x][tmp.y]+1;
                }
            }
        }
    }



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

        arr = new Node[N][M];
        isVisited = new boolean[N][M];
        dist = new int[N][M];


        for (int i = 0; i < N; i++){
            s = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = new Node(i,j,s.charAt(j) - '0');
            }
        }

        bfs(0,0);
        System.out.println(dist[N-1][M-1]);
    }
}