[BFS] 송아지 찾기 .java

설명

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

송아지는 움직이지 않고 제자리에 있다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

입력

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

출력

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

예시 입력 1 

5 14

예시 출력 1

3

 

 

내 풀이

BFS -> 최단거리 

• visited[] 배열

이미 방문한 곳은 다시 방문하지 않도록 관리, 인덱스가 위치 값

• move[] 배열

현수가 이동할 수 있는 거리 -> +1, -1, +5

• bfs(int start)

큐에 (현재 위치, 점프 횟수)를 저장 

-> 각 위치에 도달할 때마다 점프 횟수를 1씩 증가, 목표 위치에 도달하면 그 점프 횟수를 반환

 

즉, e라는 목표 위치까지 최소 점프로 갈 수 있는 경우를 구한다

=> BFS 활용

 

 

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




public class Main {
    static boolean[] visited = new boolean[10001];//방문여부
    static int e;
    static int[] move = {1,-1,5};//이동 가능한 거리 배열
    public static int bfs(int start) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {start, 0});//큐에 시작 위치와 점프 횟수
        visited[start] = true;//시작위치 방문처리

        while(!q.isEmpty()) {
            int[] cnt = q.poll();
            int position = cnt[0];//현재 위치
            int jump = cnt[1];//현재까지의 점프 횟수

            if(position == e) return jump;//만약 현재 위치가 송아지의 위치라면, 현재 점프 횟수를 반환

            for(int x : move) {
                int next = position + x;//현재 위치에서 이동한 후의 위치 계산
                //유효한 범위 내이며 방문하지 않았다면
                if(next>=1 && next<=10000 && !visited[next]) {
                    q.offer(new int[] {next, jump+1});//큐에 다음 위치 넣고
                    visited[next] =true;//방문 처리
                }
            }
        }
        return -1;//답이 반드시 있지만 리턴해줘야함

    }
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int s = sc.nextInt();
        e = sc.nextInt();

        System.out.print(bfs(s));


    }


}

 

다른 풀이 

나와 다르게 점프 횟수를 큐에 넣지 않고 L (레벨) 변수를 따로 두었다

또한 점프 횟수를 e와 비교하는 부분을 다음 숫자로 넘어가기 전에 비교하여 큐에서 꺼내는 작업을 하나 줄였다

지난 문제도 이 방법으로 풀었지만 적응이 안되어서 위와 같게 풀었는데 앞으로는 이렇게 풀어야겠다

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




public class Main {
    static int[] ch;
    static int e;
    static int[] dis = {1,-1,5};//이동 가능한 거리 배열
    static Queue<Integer> q = new LinkedList<>();
    public static int bfs(int s, int e) {
        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 cnt = q.poll();

                for(int x : dis) {
                    int nx = cnt + x;
                    if(nx==e) return L + 1;
                    if(nx >=1 && nx <=10000 && ch[nx]!=1) {
                        q.offer(nx);
                        ch[nx] = 1;
                    }
                }
            }
            L++;

        }
        return 0;

    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int s = sc.nextInt();
        e = sc.nextInt();

        System.out.print(T.bfs(s,e));

    }

}

 

 

💡💡

DFS보다 BFS가 더 재밌는 것 같다~!