[알고리즘/java] 송아지 찾기 1(BFS)

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

문제 :

 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

송아지는 움직이지 않고 제자리에 있다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하시오.

 

입력 : 

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

 

출력:

 점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재한다.

 

예시 입력 : 5 14

 

예시출력 : 3

 

---

현수의 위치에서 송아지 위치까지 몇 번의 점프만에 갈 수 있는지, 즉 최단거리를 묻는 문제로 BFS 알고리즘을 이용해 구현한다.

 

송아지 찾기 트리구조

예시 입력의 현수의 위치가 5이고 송아지 위치가 14이므로 루트노드는 5이다.

5에서 한 번의 점프로 갈 수 있는 위치 (+1, -1, +5)가 다음 레벨 자식 노드가 된다.

 

그리고 다시 각각의 노드에서 점프했을 때 갈 수 있는 위치를 구하는데, 이미 나왔던 위치라면(방문했던 노드라면)

쓰지 않는다. 

그렇게 찾다 보면 송아지의 위치인 14를 최초로 찾을 수 있고 현수는 세 번의 점프만에 송아지에게 갈 수 있다.

 

 

 

< 송아지 찾기 코드 (BFS) >

public class Main {

	public static int BFS(int hs, int s) {

		int[] dis = { 1, -1, 5 }; // 한 번의 점프로 갈 수 있는 위치를 구하기 위한 배열
		int[] ch = new int[10001]; // 방문 체크배열

		Queue<Integer> Q = new LinkedList<>();
		ch[s] = 1;
		Q.offer(hs);

		int L = 0; // 레벨

		while (!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				int cur = Q.poll();
				for (int j : dis) {
					int nx = cur + j;
					if (nx == s) // 점프한 위치가 송아지의 위치와 같다면
						return L + 1;
					if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
                    // 점프한 위치가 범위 내에 있는지 & 방문 안 한 위치인지
						ch[nx] = 1;
						Q.offer(nx);
					}
				}
			}
			L++;
		}
		return 0;

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int hs = scan.nextInt();
		int s = scan.nextInt();
		System.out.println(BFS(hs, s));

	}

}