송아지 찾기(BFS)

01 May 2023 in Algorithm on Java, Coding, Test

문제

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

입력

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

출력

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

입력예제

5 14

출력예제

3

입력예제

8 3

출력예제

5

해결방법

• 너비 우선 검색의 정의 → 한 번 방문한 노드는 재방문 하지 않음. 동일 레벨 선상 부터 채워 나가며 답을 찾는다.
• 더해주어야 하는 것들을 배열로 잡아서 반복. 가짓수를 점점 늘려나감.
• 1번씩 더한 것 → 동일 레벨로 잡는다.
• 첫번째 반복 :: 해당 노드 개수 만큼 자식을 만들어야 하므로 큐 사이즈만큼 돌린다. 이 때, 하위 돌릴 노드를 큐에서 꺼낸다(poll 해야 사이즈 체크 시 맞게 떨어진다.)

• 두번째 반복 :: 더해야 하는 개수 만큼 시도 한다 → 체크 배열이랑 조건 맞는지 체크해서 맞으면 넣는다.

  

코드

import java.util.*;

class Main {
    int answer = 0;
    int[] dis = {1, -1, 5};
    int[] ch;
    Queue<Integer> Q = new LinkedList<>();

    public int BFS(int s, int e) {
        // s 부터 e 까지 dis 에 정의된 값으로 최소한으로 진행해야 함.
        ch = new int[10001];
        ch[s] = 1;
        // 큐에 현재 위치를 넣는다.
        Q.offer(s);
        int L = 0;
        // 큐가 빌 때까지 반복한다.
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                // 큐에서 꺼낸다. -> 현재 위치
                int x = Q.poll();
                // 갈 수 있는 경우 만큼 반복한다.
                for (int j = 0; j < 3; j++) {
                    // 현재 위치에 갈 수 있는 경우를 더한다.
                    int nx = x + dis[j];
                    // 그 값이 송아지 위치이면 리턴한다.
                    if (nx == e) {
                        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) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        int s = kb.nextInt();
        int e = kb.nextInt();
        System.out.println(T.BFS(s, e));
    }
}