[Inflearn] 자바 알고리즘 문제풀이 #07-08 8. 송아지 찾기(BFS : 상태트리탐색)

문제

설명

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

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

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

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

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

 

입력 

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

 

출력 

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

예시 입력 1 

5 14

예시 출력 1

3

 

 

 

내 풀이

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

public class Main7_8 {
    int answer=0;
    int direction[] = {1, -1, 5};
    int[] check = new int[10001];
    Queue<Integer> Q = new LinkedList<>();
    public int BFS(int s, int e){
        int L=0;
        check[s] = 1;
        Q.offer(s);
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                int cur = Q.poll();
                if(cur==e) return L;

                for (int j = 0; j < 3; j++) {
                    int x = cur + direction[j];
                    if(check[x]==0) {
                        check[x] = 1;
                        Q.offer(x);
                    }
                }
            }
            L++;
        }
        return 0;
    }

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

time limit,,,

 

 

for문을 아래와 같이 고치니 정답이었다.

for (int j = 0; j < 3; j++) {
    int x = cur + direction[j];
    if(check[x]==0 && x>=1 && x<=10000 ) {
        check[x] = 1;
        Q.offer(x);
    }
}

문제에서 주어지는 조건을 반영하는 건 자꾸 까먹는다

"직선의 좌표 점은 1부터 10,000까지"라고 명시되어 있으니 조건문에서 제한을 걸어주어야 시간 안에 동작할 수 있다!

 

 

 

선생님 풀이

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

public class Main7_8 {
    int answer=0;
    int dis[] = {1, -1, 5};
    int[] ch;
    Queue<Integer> Q = new LinkedList<>();
    public 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 x = Q.poll();
                if(x==e) return L;
                for (int j = 0; j < 3; j++) {
                    int nx = x+dis[j];
                    if(nx>=1 && nx<=10000 && ch[nx]==0) {
                        ch[nx]=1;
                        Q.offer(nx);
                    }
                }
            }
            L++;
        }
        return 0;
    }

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

 

 

 

결과