[인프런 자바/java] 8. 송아지 찾기 1(BFS : 상태트리탐색) _디버깅의 눈물

체크 포인트

 

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

-'점프의 최소 횟수'를 구하는 문제이기 때문에, 최단 경로를 구하는 BFS로 접근

 

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

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

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

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

 

// 새로운 map[newX]의 값은 이전보다 한번 점프 횟수 추가
					map[newX] = map[temp] + 1;

 

 

 

풀이

 

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


public class Main {
	
	// 현수의 위치 S, 송아지의 위치 E 
	static int S, E;
	// 현수가 송아지를 찾으러 다니는 수평선 상의 위치 배열
	static int[] map;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 현수의 위치
		S = Integer.parseInt(st.nextToken());
		// 송아지의 위치
		E = Integer.parseInt(st.nextToken());
		
		// 지도 배열 초기화
		map = new int[10001];
		
		// 현수의 위치로부터 bfs 탐색 시작
		bfs(S);
		
		
	}
	
	
	public static void bfs(int x){
		// 문제에서 '최소의 점프 수'를 요구했으므로 Queue 사용
		Queue<Integer> Q = new LinkedList<Integer>();
		
		// 현수의 초기 위치값(현수의 위치 x = 5, 현수의 위치값 map[x] = 1)
		// x=5일 때, map[5]=1로 처리하므로써 해당 위치를 방문했다고 표시
		map[x] = 1;
		
		Q.add(x);
		
		while(!Q.isEmpty()){
			// 큐로부터 꺼낸 이전 x값
			int temp = Q.poll();
			// 새롭게 탐색할 x값을 담는 변수 newX
			int newX;
			
			// 현수가 이동할 수 있는 방법에 따른 조건
			for(int i=0; i<3; i++){
				if(i==0){
					newX = temp + 1;
				}
				else if(i==1){
					newX = temp - 1;
				}
				else{
					newX = temp + 5;
				}
				
				// 새로운 x값이 송아지의 위치와 같다면,
				if(newX==E){
					// 송아지를 찾는 동안 움직였던 총 거리 수 출력
					System.out.println(map[temp]);
					return;
				}
				
				// 새로운 x(newX)가 (0~10000) 사이에 존재하고,
				// 이전에 방문한 적이 없는 위치라면 탐색!
				if(newX>=0 && newX<map.length && map[newX]==0){
					// 탐색할 newX를 큐에 넣어준다.
					Q.add(newX);
					// 새로운 map[newX]의 값은 이전보다 한번 점프 횟수 추가
					map[newX] = map[temp] + 1;
				}
			}
			
			
		}
			
	}
	
	
}