[PS] 인프런 강의 - Tree 4. 송아지 찾기 (BFS)

 

문제

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.

 

▣ 출력설명
점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.

 

▣ 입력예제 1
5 14

▣ 출력예제 1
3

 

▣ 입력예제 2
8 3
▣ 출력예제 2
5

 

풀이

BFS는 최단 거리를 구하는 방법이라는 것을 이 문제를 통해서 알 수 있다.

앞서 푼 것 처럼 넓이 우선 방식으로 순회하기 위해서 큐를 사용한다.

 

스카이 콩콩으로 이동할 수 있는 방법은 +1, -1, +5 세가지이다. 따라서 자식 노드가 3개 생긴다.

※주의: 직선의 좌표 점은 1부터 10,000 까지이므로 자식 노드를 구할 때 체크해야한다.

 

한 번 갔던 좌표는 큐에 다시 넣지 않기 위해서 ch[좌표] 배열로 구분한다. (값이 1이면 한번 간 좌표, 0이면 X)

ch[좌표] = 1일 때를 그림에서 빨간색 숫자로 구분해놨다.

 

 

입력 예제 1 을 보면

현수의 출발 좌표는 5일 때(레벨 0), 송아지 좌표가 있는 노드의 레벨 값 3이 점프의 최소 횟수이다.

 

송아지는 좌표 14에 있으며 최단거리는 레벨 3

 

코드

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

public class Main {
	
	static int[] dis = {1, -1, 5}; //스카이 콩콩
    static int[] ch;
    static Queue<Integer> Q = new LinkedList<>(); //int X Integer null 체크
    
	//레벨 탐색
	public static int BFS(int s, int e) {
		ch = new int[10001]; //좌표 점 1~10,000
		ch[s] = 1; //인덱스가 좌표, 값이 있으면 1 없으면 0
		Q.offer(s);
		int L = 0; //레벨

		while(!Q.isEmpty()){
			int len = Q.size();
			
			for(int i=0; i<len; i++) {
				int x = Q.poll(); //꺼낸다
//				if(x == e) return L; //송아지 좌표면 레벨 반환 
				
				//스카이 콩콩 방식 순회
				for(int j=0; j<dis.length; j++) {
					int nx = x + dis[j]; //자식 노드 구함
					if(nx == e) return L+1; //송아지 좌표면 레벨 반환, 여기 넣는게 더 빠름
					
					//좌표 1~10,000
					if(nx >= 1 && nx <= 10000 && ch[nx] == 0) {
						ch[nx] = 1; //ch에 추가
						Q.offer(nx); //큐에 추가
					}
				}
			}
			L++; //레벨 증가
		}
		return 0;
	}
	

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int s = in.nextInt(); //현수 위치 5 
        int e = in.nextInt(); //송아지 위치 14 
        
        System.out.print(BFS(s,e));
    }
}