[JAVA] 백준 2178 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

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

 

- 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 

- 이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 떄 지나야 하는 최소의 칸 수를 구하는 프로그램을작성하시오. 

- 한 칸에서 다른 칸으로 이동할 떄, 서로 인접한 칸으로만 이동할 수 있다, 

 

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

 

 

문제 풀이 

 

BFS로 최단거리 및 경로구하기 : 네이버 블로그 (naver.com)

BFS로 최단거리 및 경로구하기

[백준 2178/JAVA] 미로 탐색 — 위위의 개발 기록장 (tistory.com)

[백준 2178/JAVA] 미로 탐색

 

- 최단 거리 찾기 문제는 BFS로 풀이해야 한다. 

- BFS를 사용하면 출발지로부터 각 노드까지의 방문은 최단 경로로 이루어질 수 밖에 없다. 

- 큐를 사용하여 "너비 우선 탐색"을 하기 때문에 자연스럽게 출발지로부터 거리 순으로 방문이 되기 때문이다. 

 

- (1,1)에서부터 시작해서 (N,M)까지의 최단 거리를 구해야 한다 .

- BFS 탐색이므로 현재 좌표와 거리가 같은 곳은 모두 방문해서 시작노드로부터 얼마 떨어져 있는지 거리를 계산한 후 그 자리에 거리값을 저장한다. 

 

- 큐가 빌 때까지 아래 과정 반복

 

1) 큐에서 좌표 (x,y) 를 하나 꺼냄 -> (x,y)와 인접한 좌표를 모두 구한다. 즉 (x,y)의 상하좌우에 해당하는 좌표를 구한다.

2) (new_X, new_Y)가 이동가능한 곳이며, 즉, 좌표가 N*M크기를 벗어나지 않고, 값이 1이고, 아직 방문하지 않았다면

3) (new_X, new_Y)을 방문하고 (new_X, new_Y)을 큐에 넣고 방문체크를 한다. 

4) (new_X, new_Y)가 (1,1)(= 시작점)으로부터 떨어진 거리를 계산하여 그 자리에 저장한다. 

 

 

정답 

 

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

public class Main
{
    static int N,M;
    static int map[][];
    static boolean visited[][];
    static Queue<Coordinate> q = new LinkedList<>();
    
    //bfs
    static void bfs(int x, int y)
    {
       int[] dirX = {-1,1,0,0};
       int[] dirY = {0,0,-1,1};
       
       q.offer(new Coordinate(x,y)); 
       visited[x][y] = true;
       
       while(!q.isEmpty()) {
    	   Coordinate cur = q.poll(); //큐에서 객체 꺼내기
    	   
    	   //상하좌우 확인 
    	   for(int i=0; i<4; i++)
    	   {
    		   int new_X = cur.x + dirX[i];
    		   int new_Y = cur.y + dirY[i];
    		   
    		   //새로운 좌표가 N*M 범위를 넘는 노드 제외 
    		   if(new_X<0 || new_X>=N || new_Y<0 || new_Y>=M)
    			   continue;
    		   
    		   //값이 0이고, 이미 방문한 노드 제외 
    		   if(map[new_X][new_Y]==0 || visited[new_X][new_Y])
    			   continue;
    		   
    		   //새로운 좌표에 지나온 노드 수 저장 
    		   map[new_X][new_Y] = map[cur.x][cur.y]+1;
    		   //새로운 좌표의 객체 생성, 큐에 삽입 
    		   q.offer(new Coordinate(new_X,new_Y));
    		   visited[new_X][new_Y] = true;
    	   }
       }
    }
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        visited = new boolean[N][M];
        
        //map 정보 반영
        for(int i=0; i<N; i++)
        {
            String str = br.readLine();
            for(int j=0; j<M; j++)
            {
                map[i][j] = str.charAt(j)-'0';
            }
        }
        
        bfs(0,0);
        bw.write(String.valueOf(map[N-1][M-1])); //마지막 지점의 값 출력 

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

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