백준 2178번 : 미로탐색

미로 탐색은 대표 그래프 문제 중 하나이다.

 

최단 경로를 찾기 위해서 가장 작은 값으로 바꿔나가는 방식으로 생각했다. 

 

예시를 봤을 때에는

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  9  10  11  12

2  0  8  0   12  0

3  0  7  0   13  0

4  5  6   0  14  15

 

이런 식으로 채워나가면 되겠다고 생각해서 dfs로 구현을 했다.

 

하지만, dfs 로 구현했을 때 시간 초과가 계속 떴다.

 

 dfs 는 최단경로를 찾기엔 적합한 방법이 아니기 때문이다. 일단 해를 찾으면 끝나는 dfs의 특성상 최단경로라는 최적의 해를 구할 수 없을지도 모른다.  

 

밑의 글에 아주 잘 설명되어 있다.

 

www.acmicpc.net/board/view/25832

<만일 모든 경로를 탐색하지 않고 각 칸을 한 번씩만 방문한다면, 처음으로 방문한 경로가 최단 경로라는 보장이 없으니 당연히 틀립니다>

라는 걸 극복하기 위해 위 방식처럼 구현을 했으나, 아마 내가 발견하지 못한 틀린 답이 있을 것 같고, 엄청난 시간이 걸리는 걸로 보인다.

 

그래서 다시 위의 방식을 이용해 bfs로 구현했으나, 위의 방식처럼 할 필요는 없다.

 

왜냐하면 bfs 의 경우, 큐에 값을 넣을 때, 같은 레벨의 값을 넣기 때문에 사실 이미 방문한 지점은 무조건 나보다 먼저 방문했을 지점이기 때문이다.

 

1  1 1  1  1 1

1 0 1 0  1 0

1 0 1 0  1 1

1 1 1  0 1  1

 

 

큐에 들어가는 값으로 설명하면

   1번째      2번째          3번째               4번째         5번째

(0,0 ) ->   (0,1)       ->  (0,2)       ->    (0,3)    ->  (0,4) & (1,3)

                  (1,0)      ->   (2,0)      ->    (3,0)    ->  (3,1)

 

이렇게 된다. 

 

 

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main { 
    public static int[][]  arr;
    public static int cnt = 0;
    public static int n;
    public static int m;
    public static int[] dx = {1,0,-1,0};
    public static int[] dy = {0,-1,0,1};
	public static void main(String args[]) {
       
		Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
		arr = new int[n][m];
        for(int i=0;i<n;i++) {
            String temp = sc.next();
            for(int j=0;j<m;j++){
                arr[i][j] = temp.charAt(j)-'0';
                
            } 
        }
    
        bfs(0,0);
       
		System.out.print(arr[n-1][m-1]+" ");
       
        sc.close();
    }
 
    public static void bfs(int i, int j){
    	
    	Queue<Point> queue = new LinkedList<>();
    	Point point = new Point(i,j);
    	
    	queue.add(point);
    	
    	
    	while(!queue.isEmpty()) {
    		
    		for (int idx=0;idx<4;idx++){
    			int curX = queue.peek().x+dx[idx];
    	        int curY = queue.peek().y+dy[idx];
    	        if(curX >=0 && curX<n&&curY>=0 && curY<m && arr[curX][curY] == 1 ){
    	           arr[curX][curY] = arr[queue.peek().x][queue.peek().y]+1;
    	           point = new Point(curX,curY);
    	           queue.add(point);
    	        } 
    	    }
    		queue.remove();
    	}
    	
    }
    
}class Point{
	
	int x;
	int y;
	Point (int x, int y){
		this.x = x;
		this.y = y;
	}
}