[Ch.07 - BFS] 02. 송아지 찾기 (+BFS : 상대트리탐색)

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

 

설명

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

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

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

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

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

입력

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

출력

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

예시 입력 1 

5 14

예시 출력 1

3

 

---

 

문제 구현 순서

1. ds 선언
   1. answer 변수
   2. 이동 가능한 배열
   3. 이동한 위치 체크하는 배열
   4. 큐 선언
2. 초기값 설정
3. 너비우선탐색을 사용하므로,  레벨을 이용해 결과값 반환

 

#주의 사항

1. L의 선언 위치
2. L에 1을 더할 위치
3. 큐의 크기만큼도는 for루프를 선언할 때, q.size()로 직접 구현하는게 아니라, 미리 len변수로 초기화
   1. 이후에 offer를 한 다음에, 루프를 돈다면, 루프의 크기가 점점 커진다
   2. 따라서 미리 큐의 크기를 지정해, L의 크기가 올바르게 커지도록 해야한다.

---

import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner kb=new Scanner(System.in);
    int s = kb.nextInt();
    int e = kb.nextInt();
    System.out.println(solution(s,e));
  }
  static int solution(int s, int e){
    Queue<Integer> q = new LinkedList<>();
    q.offer(s);
    int cnt[] = new int[10001];
    int answer=0;
    while(!q.isEmpty()){
      int x = q.poll();
      
      final int[] check={-1,1,5};
      for(int i=0;i<3;i++){
        int nx=x+check[i];
        
        if(nx<0|| nx>10000||cnt[nx]>0) continue;
        q.offer(nx);
        cnt[nx]=cnt[x]+1;
        
        if(nx==e) 
        	return answer=cnt[nx];
      }
    }
    return answer;
  }
}

 

+) 세련된 풀이

package dfsbfs.ch07_2;
//송아지 찾기

//BFS - Binary First Search
//앞, 뒤로 1
//앞으로는 5 이동가능
//점프의 최소횟수 구하기

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

public class BFS02 {
	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[1001];
		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 < dis.length; j++) {
					int nx = x + dis[j];
					//거리 계산
					
					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) {
		BFS02 T = new BFS02();
		Scanner kb = new Scanner(System.in);
		int s = kb.nextInt();
		int e = kb.nextInt();
		System.out.println(T.BFS(s, e));
	}

}