[BFS기초] 송아지 찾기(BFS : 상태트리탐색)(인프런 알고리즘 7-8)

문제 풀이 (JAVA)

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

public class part7_8 {
	static int K; // 송아지 위치
	static int level; // 레벨(점프횟수)

	public static void main(String[] args) {
		// 송아지 찾기1(BFS)
		Scanner input = new Scanner(System.in);

		int N = input.nextInt(); // 철수의 위치
		K = input.nextInt(); // 송아지의 위치
		bfs(N);
	}

	private static void bfs(int N) {
		Queue<Integer> queue = new LinkedList<>();
		int min = Integer.MAX_VALUE; // 최소 거리 변수
		queue.offer(N); // 철수의 위치 N 삽입
		while (queue.peek() != K) { // 철수의 위치가 송아지의 위치가 아닐동안 반복
			int cur = queue.peek(); // 철수의 현재 위치 변수
			min = Integer.MAX_VALUE; // 최소 거리 변수 초기화
			queue.offer(cur + 1); // 점프 +1
			queue.offer(cur - 1); // 점프 -1
			queue.offer(cur + 5); // 점프 +5
			int len = queue.size(); // 큐의 경우 사이즈
			for (int i = 0; i < len; i++) {
				int num = Math.abs(K - queue.peek()); // 최소거리 변수(송아지의 위치-철수의 점프 후 위치)
				if (min > num) { // 최소 거리를 저장
					min = num;
				}
				queue.offer(queue.poll()); // 큐의 변수를 한바퀴 돌린다.
			}
			for (int i = 0; i < len; i++) {
				// 지정한 최소거리가 아니라면 큐에서 제거
				if (min != Math.abs(K - queue.peek())) {
					queue.poll();
				} else {
					// 지정한 최소거리라면 큐에 다시 넣는다.
					queue.offer(queue.poll());
				}
			}
			// 한번 다 돌았을시 점프후 최소거리 변수만 큐에 남음.
			level++; // 횟수 카운트 증가
		}
		System.out.print(level);
	}
}

주요 핵심 포인트

1.  점프 한번시 +1, -1 , +5 만큼 갈 수 있으므로 경우의수는 3가지가 된다. 그 중 목표값 K와 가장 가까운 값을 K- (이동한값) 중 가장 크기가 적은 값이 송아지의 위치와 가까워지므로 최소값을 Math.abs()로  구하였다.

2. 철수의 첫번째 값 N을 큐에 넣고, +1,-1,+5의 증가되는 값들을 뒤이어 차례로 넣는다.

ex) 철수의 처음 위치 = 5 라면 큐 (5 <- 6 <- 4 <- 10) , 송아지의 위치 = 14

3. 송아지의 위치와 큐에 적재되어 있는 값들 중 (송아지의 위치- 적재된 큐) 를 하여 가장 차이가 적은 값이 최적의 이동값으로 큐를 앞부터 비교하여 한번씩 재적재하여 최소값을 구한다.

ex) 14 - 5 = 9 , 14 - 6 = 8 , 14 - 4 =10 , 14 - 10 = 4   => 최소값 = 4

4.  재적재된 큐와 최소값이 일치하는지 다시 비교하여 일치하지 않는 경우 제거하고, 일치하는 경우 큐에 재적재하였다.

ex) 큐( 5 <- 6 <- 4 <-10) -> (6 <- 4 <- 10) -> (4<- 10) -> (10)

5. 최종적으로 하나의 값이 남으며 해당 값이 다음 점프 값이 되며, 점프횟수를 가리키는 level을 1 증가시킨다.

6. 1~5를 반복하여 점프한 최종 값이 송아지의 위치와 같아진다면 반복을 종료한다.

 

개선해야할 사항

1.  위처럼 생각하여 풀이하였을 때, 시간 효율성은 괜찮게 나왔다. 강의와 비교하였을때 강의에서의 시간 효율성보다 내가 풀었던 시간 효율성이 조금 더 괜찮지 않나 싶다. K의 값이 크더라도 5씩 증가하기 때문에 K/5 * 2n번을 반복하므로 모든 수를 비교하지는 않아 시간 효율성이 좋게 나온듯 하다. bfs는 최적의 경로 문제를 풀기에 적절한 문제임을 인지하자.