[알고리즘] 7-8 송아지 찾기 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다.

• 문제 설명 : 수직선상 좌표에서 현수의 위치에서 송아지의 위치까지 갈 수 있는 최소한의 점프 횟수를 구하는 문제(한 번의 점프로 앞으로 1 or 뒤로 1 or 앞으로 5 이동 가능)
• 문제 링크 : https://cote.inflearn.com/contest/10/problem/07-08

풀이

최단 경로를 구하는 문제이기 때문에 BFS(넓이우선탐색)을 사용한다.

풀이 과정을 트리 그림으로 나타내면 다음과 같다.

노드의 숫자는 좌표 위치를 뜻하고 간선 위의 숫자는 한번의 점프로 이동하는 거리를 나타낸다(불필요한 중복 좌표는 생략).

즉, 트리의 레벨이 점프 횟수를 나타내고 최초로 송아지의 위치가 발견되는 노드는 레벨 3이기 때문에 점프의 최소 횟수는 3번이다.

코드 구현

• boolean 형 checked 배열을 사용하여 탐색 과정에서 불필요한 중복 좌표를 걸러낸다.
• Queue 자료구조를 사용하여 BFS 진행

package inflearn.recursive_tree_graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//송아지 찾기(BFS : 상태트리탐색)
public class Main7_8 {

    /**
     * @param s : 현수 위치
     * @param e : 송아지 위치
     * @return : 점프의 최소 횟수
     */
    public static int bfs(int s, int e) {
        int[] distance = {-1, 1, 5}; //한번의 점프로 이동하는 거리
        boolean[] checked = new boolean[10001]; //중복되는 좌표를 걸러내기위해(직선의 좌표 점은 1~10000)
        int level = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(s);

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                int n = q.poll();

                for (int j : distance) {
                    int n2 = n + j;

                    if (n2 == e) //이동거리가 송아지의 위치 e와 같다면
                        return level+1;

                    if (n2 >= 1 && n2 <= 10000 && !checked[n2]) {
                        checked[n2] = true;
                        q.offer(n2);
                    }
                }
            }

            level++;
        }

        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        System.out.println(bfs(s, e));
    }
}