[인프런 자바/java] 11. 미로의 최단거리 통로(BFS) _디버깅의 눈물

 

 

체크 포인트

 

1. BFS(너비 우선 탐색)를 이용하는 문제

-'최단으로 움직인 칸수'를 구하는 문제이기 때문에, 최단 경로를 구하는 BFS로 접근

 

 

2. 방문과 카운팅의 동시 처리

-새로운 위치(newX)로 이동 시, 이전의 방문 위치(map[tempX][tempY])의 값에 점프 횟수 1을 추가

 

// (nx,ny) 방문 처리 및 이전 위치값+1을 통해 거리 수 카운팅
map[nx][ny]= map[tempX][tempY] + 1;

 

-어떤 map[ ][ ]의 값이 0이 아닌 경우, 기존에 방문했음을 의미

-어떤 map[ ][ ]의 값이 나타내는 숫자는 해당 지점까지 도달하기 위한 총 이동 거리를 의미

 

기본 상태의 미로

 

 

BFS 탐색이 끝난 후의 미로

 

 

 

 

 

풀이

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


public class Main {

	// 미로의 지도를 입력받는 배열
	static int[][] map;
	
	// bfs 탐색 시, 상,하,좌,우 이동 변수
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;

		// 지도 배열 초기화
		// 문제에서 (1,1)부터 시작이기 때문에 배열의 크기를 8로 선언
		map = new int[8][8];
		
		// 지도 내 값 입력
		for(int i=1; i<8; i++){
			
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int j=1; j<8; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// (1,1)부터 bfs 탐색 시작
		bfs(1,1);
		
		// 최단거리 출력
		System.out.println(map[7][7]-1);
		
	}
	
	
	public static void bfs(int x, int y){
		
		// (x,y) 방문 처리
		map[x][y]=1;
		
		Queue<Integer> Q = new LinkedList<Integer>();
		
		Q.add(x);
		Q.add(y);
		
		while(!Q.isEmpty()){

			// x,y값을 꺼낸 후,
			int tempX = Q.poll();
			int tempY = Q.poll();
			
			// 상,하,좌,우 좌표 값 적용
			for(int i=0; i<4; i++){
				int nx = tempX + dx[i];
				int ny = tempY + dy[i];
				
				// 새로운 x(nx), 새로운 y(ny)가 미로 위에 존재하고,
				if(nx>=0 && ny>=0 && nx<8 && ny<8){
					// 이전에 방문했던 적이 없다면,
					if(map[nx][ny]==0){
						// nx, ny로 탐색 시작
						Q.add(nx);
						Q.add(ny);
						// (nx,ny) 방문 처리 및 이전 위치값+1을 통해 거리 수 카운팅
						map[nx][ny]= map[tempX][tempY] + 1;
					}
					
				}
				
				
			}
		}
		
	} // end of bfs
	
	
}