8. 송아지 찾기 1 (BFS: 상태 트리 검색)

1. 문제

한 번의 점프로 앞으로 5, 1칸 뒤로 1칸갈 수 있다.

현수의 위치 S와 송아지의 위치 E가 주어졌을 때 

현수가 송아지의 위치까지 도달할 점프의 최소 횟수를 구하시오.

 

입력

5 14

 

출력

3 

 

 

2 - 1. 나의 풀이

이전 강의에서 BFS에 대한 이해를 위해선 송아지 찾기 문제가 좋다해서 이전 강의를 보고 바로 이 문제를 풀려고 왔다.

 

answer = E - S 라 하고

0에서 부터  +5, +1, -1 만의 수식으로 answer까지 가는데 걸리는 최소 회수를 구하는 문제와 같다.

 

큐에 맨처음 0을 넣고

0에 5를 더한 값, 1을 더한 값, 1을 뺀값을 넣는다.

큐를 poll해서 answer와 같은지 확인하고 아니면 위 과정을 반복한다.

poll한 값이 answer이면 해당 계층을 반환하고 끝낸다.

 

위 코드를 실행 했을 때 시간 초과가 났다.

이유는 아무런 조건 없이 매번의 계층마다 3가지의 tree가 생겨났고 계층이 지날 수록 생겨난 tree의 수는 3의 제곱으로 생겨나기 때문에 조금만 큰 수를 입력받으면 시간초과가 나는 것이다.

 

이를 해결하기 위해 조건을 걸었다.

큐에서 poll한 값을 tmp라고 하자.

answer - tmp >= 5 이면 5를 더한 값만 큐에 넣고

아니면 1을 더하고 뺀 값만 큐에 넣는것이다.

이렇게 하면 계층에 비례해 생겨난 tree의 수가 3의 제곱수에서 한 두개로 줄어든다.

 

이렇게 코드를 다시 작성하니 시간 초과가 나지 않고 통과했다.

 

다른 유튜브에서 본건데 BFS로 구하는 답은 항상 최소 횟수의 답이다.

첫번째 계층에서의 모든 경우의수

그 다음 계층에서의 모든 경우의 수를 구하는 방식이기 때문이다.

2 - 2. 나의 코드

맨 처음 시간초과가 났던 코드

package BFS_DFS;
import java.util.*;

public class BFS08_findCalf {
    static int answer;

    public static void BFS(int num) {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(num);
        int L =0; //계층
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
            int tmp = Q.poll();
                if(tmp == answer) {
                    System.out.println(L);
                    return;
                }
                else { 
                //무분별 하게 큐에 3제곱 만큼 넣는게 시간초과의 원인
                 Q.offer(tmp + 5);        
                 Q.offer(tmp + 1);
                 Q.offer(tmp - 1);
                   }
                }
            }
            L++;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int E = sc.nextInt();
        answer = E - S; //0에서 부터 찾아야할 답

        BFS(0);
    }
}

 

조건을 만들어서 해결

package BFS_DFS;
import java.util.*;

public class BFS08_findCalf {
    static int answer;

    public static void BFS(int num) {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(num);
        int L =0; //계층
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
            int tmp = Q.poll();

                if(tmp == answer) {
                    System.out.println(L);
                    return;
                }
                else { //조건을 달아서 시간초과 해결
                   if(answer - tmp >= 5){
                       Q.offer(tmp + 5);
                   }else{
                 Q.offer(tmp + 1);
                 Q.offer(tmp - 1);
                   }
                }
            }
            L++;
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int E = sc.nextInt();
        answer = E - S; //0에서 부터 찾아야할 답

        BFS(0);
    }
}

 

3 - 1. 강의 풀이

강의에서는

불필요한 방문을 줄이기위해(시간 초과 방지) 

숫자를 더했을 때 해당 수를 이전에 방문했는지 안했는지 나타내는 체크 배열을 사용했다.

 

내 방식으로 푸는게 더 좋을거 같다는 생각이 든다?

 

문제에 별 다른 조건이 없을 때는 나처럼 간단하게 풀 수 있지만, 그렇지 않은경우는 강의처럼 푸는게 좋을거 같다.

 

 

3 - 2. 강의 코드

package BFS_DFS;
import java.util.*;


public class BFS08_solution {
    static int answer = 0;
    static int[] dis = {-1, 1, 5};
    static int[] ch; //불필요한 방문을 줄이기 위해 해당 수를 방문했는지 확인하는 check배열
    static Queue<Integer> Q = new LinkedList<>();

    public static int BFS(int s, int e) {
        ch = new int[10001]; //값은 1~ 10000까지므로
        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]; //{-1, 1, 5}를 더한다. 
                    if(nx == e) return L + 1; //더한 값이 e(송아지 위치)라면 끝
                    if (nx > 1 && nx < 10000 && ch[nx] == 0) { //
                        ch[nx] = 1;
                        Q.offer(nx);
                    }
                }
            }
            L++;

        }


        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int e = sc.nextInt();


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

 

4. 얻어갈 점

BFS 알고리즘은 최단 거리를 구하는 알고리즘