섹션 7 Recursive, Tree, Graph - 8. 송아지 찾기(BFS : 상태트리탐색)

📌 문제 설명

현수가 잃어버린 송아지를 찾기 위해 최소 점프 횟수를 구하는 문제이다.
현수는 한 번의 점프로 +1, -1, +5만큼 이동할 수 있고, 송아지는 움직이지 않는다.
두 위치가 주어졌을 때, 최소 점프 횟수를 출력한다.

---

📝 입력 & 출력

입력

• 첫 번째 줄에 두 정수 S와 E가 주어진다. (1 ≤ S, E ≤ 10,000)
  S는 현수의 위치, E는 송아지의 위치

출력

• 현수가 송아지에게 도달하기 위한 최소 점프 횟수를 출력한다.

---

🔹 예제 입력 & 출력

예제 입력

5 14

 

예제 출력

3

• 이동 경로: 5 → 6 → 7 → 14
  또는 5 → 10 → 9 → 14

---

💡 해결 방법

이 문제는 최단 거리를 구해야 하므로
DFS가 아닌 BFS(넓이우선탐색)를 사용해야 한다.

• 각 위치를 노드, 이동을 간선으로 생각할 수 있다.
• 현재 위치에서 다음 위치로 갈 수 있는 경우는 +1, -1, +5
• BFS를 이용해 가까운 위치부터 차례로 탐색하면 최소 횟수를 먼저 찾게 된다.

---

💻 코드 구현 (Java)

전체 코드

package partRecursiveTreeGraph;

import java.util.*;

public class Problem8 {	
	public int BFS(int s, int e) {
		boolean[] ch = new boolean[10001];
		int[] dis = {1, -1, 5};
		Queue<Integer> Q = new LinkedList<>();
		
		int L = 0;
		Q.offer(s);
		ch[s] = true;
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for(int i=0; i<len; i++) {
				int current = Q.poll();
				for(int d: dis) {
					int next = current + d;
					if(next == e) return L+1;
					if(next>=1 && next<=10000 && !ch[next]) {
						ch[next] = true;
						Q.offer(next);
					}
				}
			}
			L++;
		}
		return 0;
	}
	
	public static void main(String[] args) {
		Problem8 T = new Problem8();
		Scanner kb = new Scanner(System.in);
		int s = kb.nextInt();
		int e = kb.nextInt();
		System.out.print(T.BFS(s, e));
		kb.close();
	}	
}

---

📖 코드 설명

1️⃣ 이동 규칙 설정 & 방문 체크 배열

boolean[] ch = new boolean[10001];
int[] dis = {1, -1, 5};

• 현수가 이동할 수 있는 값들: +1, -1, +5
• ch[i] == true면 i 위치는 이미 방문한 위치 → 중복 탐색 방지

---

2️⃣ BFS를 위한 큐 초기화

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

• 현수의 시작 위치를 큐에 넣고 방문 처리

---

3️⃣ BFS 실행: 레벨 단위 탐색

while(!Q.isEmpty()) {
	int len = Q.size();
	for(int i=0; i<len; i++) {
		int current = Q.poll();
		for(int d: dis) {
			int next = current + d;
			if(next == e) return L+1;
			if(next>=1 && next<=10000 && !ch[next]) {
				ch[next] = true;
				Q.offer(next);
			}
		}
	}
	L++;
}

• 다음 위치가 송아지 위치면 → 현재 레벨 + 1 반환
• 1~10,000 범위를 벗어나지 않고 방문하지 않은 경우만 큐에 추가

---

⏳ 시간 복잡도 분석

• 현수가 이동 가능한 모든 위치 수는 최대 10,000개
• 각 위치에서 최대 3가지 이동을 시도
• 총 시간 복잡도: O(N) (N = 10,000 이하, BFS는 모든 노드를 1번씩 탐색)

---

🧠 핵심 정리

• BFS는 최단 거리 문제에 적합하다.
• 레벨 단위 탐색을 통해 몇 번 만에 송아지를 찾을 수 있는지 구한다.
• 중복 방문을 막기 위해 boolean[] 방문 배열을 사용한다.
• 시간 복잡도는 O(N)으로 매우 빠르다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

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