알고리즘) 송아지 찾기 1(BFS : 상태트리탐색)

문제

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

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

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

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

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

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

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

 

최초 작성 코드(Timeout)

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

public class Main {
    Node header;

    static class Node {
        int data;

        public Node(int data) {
            this.data = data;
        }
    }

    public Main() {
        this.header = null;
    }

    void findCalf(int e) {
        // 1, -1, 5만큼 이동하는 경로 세 가지로 계속 트리 전개
        Node root = header;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node n = q.poll();
                if (n.data == e) {
                    System.out.println(cnt);
                    return;
                }

                q.offer(new Node(n.data - 1));
                q.offer(new Node(n.data + 1));
                q.offer(new Node(n.data + 5));
            }
            cnt++;
        }
    }


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

        Main tree = new Main();
        // tree root
        tree.header = new Node(sc.nextInt());
        // node 값이 아래 값이 되는 모든 경로 중에 가장 낮은 단계 출력
        int e = sc.nextInt();

        tree.findCalf(e);
    }
}

 

개선 코드

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

// 송아지 찾기(최단거리 알고리즘)
public class Main {
    int[] checked = new int[10001];
    int[] arr = {1, -1, 5};
    void findCalf(int s, int e) {
        // 1, -1, 5만큼 이동하는 경로 세 가지로 계속 트리 전개
        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        checked[s] = 1;

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int n = q.poll();

                for (int j = 0; j < 3; j++) {
                    int x = n + arr[j];
                    if (x >= 1 && x <= 10000 && checked[x] == 0) {
                        if (x == e) {
                            System.out.println(cnt + 1);
                            return;
                        }
                        if (n < e && x == -1) continue;
                        q.offer(x);
                    }
                }
            }
            cnt++;
        }
    }


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

        Main tree = new Main();
        int s = sc.nextInt();
        int e = sc.nextInt(); // node 값이 아래 값이 되는 모든 경로 중에 가장 낮은 단계 출력

        tree.findCalf(s, e);
    }
}

 

시간 단축을 위해 신경쓴 부분

• 이미 넣었던 값은 넣지 않아야 불필요한 전개를 막을 수 있으므로 체크리스트 배열 생성
• 큐에 넣었다가 빼는 시기에 해당 값이 일치하는지를 확인하는 것보다 큐에 넣기 전에 확인하는 것이 더 빠르다.