자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(BFS_송아지 찾기1)

 

 

8. 송아지 찾기1(BFS)

 

예시 입력 1 

5 14

예시 출력 1

3

 

이전에 찾았던건 무시해줍니다. 최초로 발견되는게 최단거리 입니다.

14까지 3번만에 갈 수 있다는 것입니다

5 -> 4 -> 9 -> 14

 

 

이런걸 상태 트리라고 합니다.

3레벨 탐색하니까 14번을 발견하고 루트에서 몇번만에 갔는지를 출력하면 됩니다.

 

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

// 최단 거리 구하기
public class Main {
    int answer = 0; // 최소 횟수 카운팅
    int[] dis = {1, -1, 5}; // 앞으로 전진, 뒤로 후진, 5칸 앞으로 전진
    int[] ch; // 체크 배열 : 한 번 방문한건 재방문x - 시간복잡도 늘어나지 않게
    Queue<Integer> Q = new LinkedList<>(); // 정수를 저장할 수 있는 Queue를 전역으로 생성

    public int BFS(int n, int m ) {
    	// 좌표 점이 1부터 10,000까지라서, 인덱스번호는 10,000까지 나와야함
        ch = new int[10001];
        ch[n] = 1; // 큐에 넣을 출발 지점
        Q.offer(n);
        int L = 0;
        while (!Q.isEmpty()) {
            int len = Q.size(); // 레벨에 있는 원소 개수들
            for (int i = 0; i < len; i++) {
                int x = Q.poll();
//                if (x == m) return L; // 여기서 리턴 해줘도 되지만 3줄 밑에서 리턴
                for (int j = 0; j < 3; j++) {
                    int nx = x+dis[j]; // 자식노드 - 각 dis만큼 움직임
                    if (nx == m) return L+1; // 큐에 담기전에 리턴
                    // 계산하다가 음수가 되거나 10000을 넘는 경우를 제외
                    if (nx >=1 && nx <= 10000 && ch[nx] == 0) {
                        ch[nx] = 1; // 방문했다고 체크
                        Q.offer(nx);
                    }
                }
            }
            L++;

        }
        return  0;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 현수 위치
        int m = sc.nextInt(); // 송아지 위치
        System.out.println(T.BFS(n,m));

    }
}

 

16번 라인에서 리턴하는거 말고, 18번 라인에서 자식을 찾을 때 송아지 위치랑 똑같다면 리턴해주는 걸로 해주면 된다.