[Algorithm] 송아지 찾기1(BFS:상태트리탐색)

설명

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면

현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

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

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

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

 

입력

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다.

직선의 좌표 점은 1부터 10,000까지이다.

 

출력

점프의 최소횟수를 구한다.

답은 1이상이며 반드시 존재합니다.

 

 

 

풀이.

public class Main {

    int[] arr = {1, -1, 5}; // 뻗어나갈 3가지 자식노드
    Queue<Integer> Q = new LinkedList<>();

    public int BFS(int s, int e) {

        int[] check = new int[10001]; // 한번 들렸었던 좌표인지 유무 체크 (0과 1)
        check[s] = 1; // 현수의 시작위치는 1로 체크하고 시작
        Q.offer(s); // 트리 최상단 현수의 위치를 Q에 넣고 시작
        int Level = 0; // 트리 최상단 기준 0레벨로 시작, 아래 노드로 갈수록 +1
        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++) {
              	    // 큐에서 꺼낸 좌표를 기준으로 3가지의 자식 좌표 생성 (1, -1, 5)
                    int nx = x + arr[j];
                    // 생성된 좌표가 송아지 좌표와 같으면 종료. level+1 리턴.
                    if(nx == e) return Level+1;
                    // 아래 (nx <= 10000 && nx >= 1) 조건여부로 유무로 runtime 발생함
                    if (check[nx] == 0 && nx <= 10000 && nx >= 1) { 
                        Q.offer(nx);
                        check[nx] = 1; // 한번 들린 좌표가 되므로 1로 체크
                    }
                }
            }
            Level++; // level은 트리형식의 최상단 0부터 말단 n까지
        }
        return 0;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        Main T = new Main();
        int s = sc.nextInt();
        int e = sc.nextInt();
        System.out.println(T.BFS(s, e));

    }
}

 

---

 

정리 :

펜과 노트로 직접 트리를 그려가면서 어떻게 로직을 구상할지 연습하는게 중요한 것 같다.