[백준] 2178 : 미로 탐색 JAVA 풀이

 

최단 거리를 구하는 문제는 bfs를 사용하기

 

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

public class Main {
	static class Point{
		int x;
		int y;
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	// 상하좌우로 이동할 때 사용할 방향배열
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	
	static int[][] graph;
	static boolean[][] visit;
	static int N;
	static int M;
	static Queue<Point> queue = new LinkedList<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		graph = new int[N+1][M+1];
		visit = new boolean[N+1][M+1];
		
        // 그래프 초기화
		for(int i=1;i<=N;i++) {
			String str = br.readLine();
			for(int j=1;j<=M;j++) {
				graph[i][j] = str.charAt(j-1)-'0';
			}
		}
        
        // 시작점인 (1,1)를 큐에 넣어줌
		queue.offer(new Point(1,1));
        
        // bfs한 결과 출력
		System.out.println(bfs());
		
	}
	
	static int bfs() {
    	// 큐가 빌 때까지 반복
		while(!queue.isEmpty()) {
        
        	// 큐에서 값 하나를 꺼냄
			Point p = queue.poll();
			
			int x = p.x;
			int y = p.y;
            
            // (x, y)를 방문했다고 체크
			visit[x][y] = true;
			
			for(int i=0;i<4;i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				
                // 범위 내에서 이동 가능한 곳이 있다면
				if(nx>0&&ny>0&&nx<=N&&ny<=M) {
					if(graph[nx][ny]==1) {
                    
                    	// 새로운 위치를 큐에 넣음
						queue.offer(new Point(nx,ny));
                        
                        // 이전 위치의 값 +1을 해서 지금까지 지나온 칸의 개수를 기록
						graph[nx][ny] = graph[x][y]+1;
                        
                        // 방문했다고 체크
						visit[nx][ny] = true;
					}
				}
			}
		}
        // (N, M)까지 오는 데에 걸린 칸 수를 반환
		return graph[N][M];
	}

}