송아지 찾기1 (BFS)

설명

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

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

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

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

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

 

입력

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

 

출력

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

 

예시 입력 1 

5 14

 

예시 출력 1

3

 

문제 해결

 

최단 거리 문제이므로 BFS를 사용하는 게 적합하다.

각 점프를 하나의 노드로, 점프 가능한 위치를 연결된 노드로 생각하여 BFS를 적용했다.

 

static int[] dis = {1, -1, 5};
static int[] ch;
static Queue<Integer> queue = new LinkedList<>();

• dis[ ]: 가능한 점프 거리를 배열로 저장한다. {1, -1, 5}
• ch [ ]: 각 위치의 방문여부를 체크한다.
• queue: BFS 탐색을 위해 큐를 사용한다.

public static int BFS(int s, int e) {
    ch = new int[10001]; //인덱스 번호이므로 +1까지
    ch[s] = 1;
    queue.offer(s);
    int L = 0;
    while (!queue.isEmpty()) {
        int len = queue.size();
        for (int i = 0; i < len; i++) { //레벨마다 큐에 len 개수만큼 들어가 있음
            int x = queue.poll();
            for (int j = 0; j < 3; j++) {
                int nx = x + dis[j];
                if (nx == e) return L+1; //queue에 넣으려고 하는 값이 e이면 return L+1
                if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
                    ch[nx] = 1; //방문했다고 표시
                    queue.offer(nx); //큐에 nx 넣음
                }
            }

        }
        L++;
    }

    return 0;
}

 

• 우선 처음의 위치 s를 큐에 넣고 방문했다는 처리를 한다.
• 레벨마다 큐에 len 개수만큼 들어가있으므로 현재 큐의 크기(len)만큼 반복하여, 현재 레벨에 해당하는 모든 노드를 처리한다.
  • 각 노드에서 3가지 점프를 시도할 수 있다. {1, -1, 5}
  • nx는 점프 후의 위치이고 이는 x에 dis[j]를 더하면 나오는 값이다. (x는 현재 위치, dis[j]는 점프하는 칸 수 이므로)
  • 그 때의 결과가 송아지의 위치와 같다면 현재 레벨+1을 반환한다. (아직 레벨 증가가 반영되지 않은 상태이므로)
  • nx가 유효 범위 내에 있고 아직 방문하지 않았다면 방문 처리를 해주고 큐에 추가한다.
• 그리고 다음 레벨로 넘어간다.
• 위 과정을 큐가 비어있지 않는 동안 반복해주면 된다.

 

최종 코드

 

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

public class P08_송아지찾기1_BFS {

    static int[] dis = {1, -1, 5};
    static int[] ch;
    static Queue<Integer> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int e = in.nextInt();
        System.out.println(BFS(s,e));

    }

    public static int BFS(int s, int e) {
        ch = new int[10001]; //인덱스 번호이므로 +1까지
        ch[s] = 1;
        queue.offer(s);
        int L = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) { //레벨마다 큐에 len 개수만큼 들어가 있음
                int x = queue.poll();
                for (int j = 0; j < 3; j++) {
                    int nx = x + dis[j];
                    if (nx == e) return L+1; //queue에 넣으려고 하는 값이 e이면 return L+1
                    if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
                        ch[nx] = 1; //방문했다고 표시
                        queue.offer(nx); //큐에 nx 넣음
                    }
                }

            }
            L++;
        }

        return 0;
    }
}