[인프런] 07_08 송아지 찾기 (BFS : 상대트리탐색)

📖  문제

---

• 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.
  • 송아지는 움직이지 않고 제자리에 있다.
  • 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.
  • 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

⚠️  주의사항

---

• BFS 이해
• 좌표가 1 ~ 10000 존재
• 송아지는 움직이지 않는다.

 

✍️  이해

---

/**
 * 1. 출발 지점인 s, 도착 지점 e 입력2
 * 2. 1~10000 이므로 ch는 int[100001], 1,-1,5칸 배열 및 체킁요 배열 입력
 * 3. Queue를 사용해서 s를 queue 추가
 * 4. queue가 빈 공간이 될 때까지 반복
 *  4-1. 길이를 queue.size()
 *  4-2. 0 ~ len 까지 반복
 *   4-2-1. x = queue.poll();
 *   4-2-2. 0 ~ 3번 반복 (자식의 숫자가 3개까지 나오기 때문)
 *    4-2-2-1. nx = x + dis[0~3]
 *    4-2-2-2. nx == e -> return line + 1;
 *    4-2-2-3. nx가 1보다 크거나 10000보다 작고 ch[nx] == 0 -> ch[nx] = 1, queue.offer(nx)
 *  4-3. line++;
 */

 

✏️  풀이

---

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

public class Main {
    int[] dis = {1, -1, 5};
    int[] ch; // 체크용 배열
    Queue<Integer> queue = new LinkedList<>();

    public int BFS(int s, int e) {
        ch = new int[100001];

        queue.offer(s);
        int line = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();

            for (int i = 0; i < len; i++) {
                int x = queue.poll();

                for (int j = 0; j < 3; j++) {
                    int nx = x + dis[j]; // 자식 숫자들 +1 -1 +5
                    if (nx == e) return line + 1;

                    if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
                        ch[nx] = 1;
                        queue.offer(nx);
                    }
                }
            }
            line++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt(); // 출발
        int e = sc.nextInt(); // 도착
        System.out.println(T.BFS(s, e));
    }
}

---