[백준] 2178 미로탐색(JAVA)

풀이

 학교 알고리즘 시간에 배웠던 미로탐색 문제인줄 알고 단순히DFS로 접근해서 모든경로의 이동수를 리스트에 저장하여 그중 가장 작은 수를 출력할려고 했다. 그러나 시간초과로 인해. 어떡게 풀어야 좋을지 몰랐다. 그래서 찾아보고 그러니 정답은 DFS가 아닌 "BFS"였다. 그러면서 다른 블로그에서는 최단, 최소를 찾을때는 BFS를 통해 구한다고 하여서 왜 그런지 몰랐다. 그러다 어느 블로그를 찾게 되었고 그 곳에 자세한 설명이 있었다. 

 

 간략하게 설명을 하면

BFS에선 간선(u,v)를 통해서, 정점 v를 처음발견해 큐를 넣었다고 가정한다. 이때, 시작점에서 v까지의 최단거리는 distanc[v]는 , 시작점에서 u까지의 최단거리 distance[u]에다가 1을 더한것이다.

조금더 풀어쓰자면

1. distance[v]가 distance[u]+1 보다 클수없음은 분명하다. 시작점부터 u까지의 경로에서 (u,v) 간선 하나를 더 붙이면 distance[u]+1 길이의 경로가 나오기 떄문이다.

 

2. 만약 distance[v]가 distance[u]+1보다 짧다고 가정을 한다면 이 경로상에서는 v바로 이전의 정점이 distance[u] + 1보다 작아야 한다(큐에서는 시작점에 가까운 순서부터 들어가므로..) 그럴려면 v는 u보다 이전에 방문되어야 하는데 이는 (u,v)를 통해 v를 방문했다는 가정과 모순이된다.

 

위와 같은 개념을 통해 BFS로 구한 경로는 최단, 최소가 되는것이다. 더불어 도착 지점에 도착하면 바로 종료하고 길이를 출력하면 된다. 다시 문제로 돌아와서 이 문제는 살짝 DP같은 느낌으로 해주면 된다. 무슨 말이냐 하면 map을 정수형 배로 선언하고 그 다음 그 이전값 +1로 증가 시켜주면 된다. 

 

<시작할때의 map>                 <도착지점에서의 map>
110110                                 120890
110110                                 230780
111111                                 345678
111101                                 456709

숫자는 방문한 순서라고 생각하면 될듯하다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    public static int[][] map;
    public static boolean[][] visited;
    public static int col, row;
    public static Stack<String> stack;
    public static ArrayList<Integer> list = new ArrayList<Integer>();
    public static int cnt;
    public static int[] dr_x = {-1, 0, 1, 0};
    public static int[] dr_y = {0, 1, 0, -1};

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

        col = Integer.parseInt(st.nextToken());
        row = Integer.parseInt(st.nextToken());
        map = new int[col][row];
        visited = new boolean[col][row];
        String s;
        for (int i = 0; i < col; i++) {
            s = br.readLine();
            for (int j = 0; j < row; j++)
                map[i][j] = s.charAt(j) - '0';
        }

        BFS(0, 0);
    }

    public static void BFS(int x, int y) {
        Queue<point> queue = new LinkedList<point>();
        queue.offer(new point(x,y));
        visited[x][y] = true;
        cnt=1;

        int temp_x = 0;
        int temp_y = 0;

        while(!queue.isEmpty()){
            point cur = queue.poll();
            if(cur.getX() == col-1 && cur.getY() == row -1) {
                System.out.println(map[col-1][row-1]);
                return;
            }
            for(int i=0; i<4; i++){
                temp_x = cur.getX() + dr_x[i];
                temp_y = cur.getY() + dr_y[i];

                if(temp_x < 0 || temp_y <0 || temp_x >= col || temp_y >= row)
                    continue;
                if(visited[temp_x][temp_y] || map[temp_x][temp_y]==0)
                    continue;

                map[temp_x][temp_y] = map[cur.getX()][cur.getY()] + 1;
                queue.offer(new point(temp_x, temp_y));
                visited[temp_x][temp_y] = true;
            }
        }
    }

    static class point{
        private int x;
        private int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

}