[PS] 인프런 강의 - BFS 1. 미로의 최단거리 통로

 

문제

7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로의 길이는 12이다.

 

▣ 입력설명
첫 번째 줄부터 7*7 격자의 정보가 주어집니다.

 

▣ 출력설명
첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

 

▣ 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

 

▣ 출력예제 1
12

 

풀이

그래프 최단 거리 구했던 것과 비슷하게 풀면 된다. (큐 사용) 큐에서 꺼냈을 때 갈 수 있는 길은 기록해두기 위해 큐의 맨뒤에 다시 집어넣는다. 그러면 다음 레벨(거리+1) 이 됐을 때 다시 꺼내진다.

 

이번에는 x, y 값 두 개를 큐에 저장해야하므로 java.awt.Point 클래스를 사용한다. 참고 직접 만들어도 상관없음.

 

지나온 길은 미로 배열의 값을 1로 바꾼다. 레벨 별 거리 누적합을 저장할 이차원 배열 dis를 선언해서 답은 dis[7][7]이다.

 

주의: 도착 지점에 오면 사방이 막혀있으므로 자동으로 함수가 종료된다. 따라서 체크할 필요 없음!

 

코드

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[][] board, dis;
	
	public static void BFS(int x, int y) {
		Queue<Point> Q = new LinkedList<Point>();
		Point point= new Point(x,y);
		Q.offer(point); //큐에 넣는다
		board[x][y] = 1; //출발
		
		while(!Q.isEmpty()){
			Point cv = Q.poll(); //꺼낸다 (현재 지점)
			
			for(int i=0; i<4; i++) {
				int nx = cv.x + dx[i];
				int ny = cv.y + dy[i];
				
				if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny] == 0) {
					Q.offer(new Point(nx, ny)); //큐에 넣는다
					board[nx][ny] = 1; //방문
					dis[nx][ny] = dis[cv.x][cv.y] + 1; //거리 누적합(주의: cv가 현재지점)
				}
			}
		}
	}
 
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        board = new int[8][8]; //출발점이 1,1
        dis = new int[8][8];
        for(int i=1; i<=7; i++) {
        	for(int j=1; j<=7; j++) {
        		board[i][j] = in.nextInt();
        	}
        }
        
        BFS(1, 1);
        if(board[7][7] == 0) System.out.println(-1); //도착할 수 없으면
        System.out.println(dis[7][7]);
        
    }
}