[백준 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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

---

정답

처음에는 깊이 탐색으로 원하는 좌표까지 가는동안 걸린 거리를 측정했다. 근데 생각해보니 그 길이 가장빠르 길이 아니라는 것을 알고 너비탐색(BFS)로 풀었다.
처음 (1,1) 좌표의 값을 1로 두고 그 주변에 갈수있는 값을 +1한 2값을 넣었다. 그렇게 주변의 갈수있는 칸에 그 칸까지 가기위해 거쳐야하는 칸의 갯수(사실상 가장 가까운 거리)를 입력하면서 탐색하다가, 원하는 좌표에 닿으면 출력하고 끝나게 했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static class Graph{
        //목표좌표
        private int N,M;
        //미로를 구성할 배열
        private int[][] maze;
        //생성자
        //미로 크기 생성
        public Graph(int n, int m) {
            this.maze = new int[n+2][m+2];
            this.N = n;
            this.M = m;
        }
        //미로 구성 함수
        public void addMaze(int row, int[] m) {
            for(int i=0; i<m.length; i++) {
                maze[row][i+1] = m[i];
            }
        }

        //너비우선 탐색
        //BFS
        //while함수로 구현
        //시작위치 (v,w)
        public void BFS(int v, int w) {
            int length = 0;
            //미로중에 방문한 칸은 1로 만든다. 각 칸 마다 깊이를 적을 거임
            maze[v][w] = ++length;

            //BFS구현을 위한 queue생성
            Queue<Node> queue = new LinkedList<Node>();

            //현재 방문한 위치 큐에 넣음
            queue.add(new Node(v,w));

            //큐가 빌때까지 반복
            while(!queue.isEmpty()) {
                Node n = queue.poll();
                if(n.v == N && n.w == M) {
                    System.out.println(maze[n.v][n.w]);
                    break;
                }

                //꺼낸 좌표의 주변 좌표중 길이 있는 것들의 값을 이전 좌표 깊이의 +1해서 저장
                if(maze[n.v-1][n.w] == 1 && (n.v-1 != 1 || n.w !=1) ) {
                    queue.add(new Node(n.v-1, n.w));
                    maze[n.v-1][n.w] = maze[n.v][n.w]+1;
                }
                if(maze[n.v+1][n.w] == 1 && (n.v+1 != 1 || n.w !=1)) {
                    queue.add(new Node(n.v+1, n.w));
                    maze[n.v+1][n.w] = maze[n.v][n.w]+1;
                }
                if(maze[n.v][n.w-1] == 1 && (n.v != 1 || n.w-1 !=1)) {
                    queue.add(new Node(n.v, n.w-1));
                    maze[n.v][n.w-1] = maze[n.v][n.w]+1;
                }
                if(maze[n.v][n.w+1] == 1 && (n.v != 1 || n.w+1 !=1)) {
                    queue.add(new Node(n.v, n.w+1));
                    maze[n.v][n.w+1] = maze[n.v][n.w]+1;
                }
            }

        }
        class Node{
            int v;
            int w;
            public Node(int v, int w) {
                this.v= v;
                this.w = w;
            }
        }

    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuffer sf = new StringBuffer();

        String[] NM = br.readLine().split(" ");

        Graph g = new Graph(Integer.parseInt(NM[0]),Integer.parseInt(NM[1]));

        for(int i=0; i<Integer.parseInt(NM[0]); i++) {
            String miro = br.readLine();
            int [] mm = new int[Integer.parseInt(NM[1])];
            for(int j=0; j<miro.length(); j++) {
                mm[j] = Integer.parseInt(miro.substring(j, j+1));
            }
            g.addMaze(i+1, mm);
        }
        g.BFS(1, 1);

        br.close();
        bw.flush();
        bw.close();
    }
}