[BFS] 8. 송아지 찾기1(BFS : 상태트리탐색)
Q. 개념
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아
지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음
과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수
있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성
하세요.
▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000
까지이다.
▣ 출력설명
점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.
▣ 입력예제 1
5 14
▣ 출력예제 1
3
▣ 입력예제 2
8 3
▣ 출력예제 2
5
전략
- BFS(레벨탐색)는 (이진트리를 포함한 상태트리에서) 주로 최단거리 알고리즘에 사용된다.
최단거리 알고리즘 키워드
"최소 횟수인 거리~" - 5가 루트노드이고, 한 루트노드에서 다음 레벨(=한번의 점프)로 가기위한 경우의 수는 세가지(1, -1, 5)이다. 14를 찾을때 까지 계속 다음레벨로 뻗는다.
- 점프 횟수 = 레벨
- 단, 시간복잡도를 줄이기 위해 이미 나온 숫자(=이미 방문한 노드)는 큐에 넣지 않는다.
- 트리구조
정답
import java.util.*;
class Main {
int answer=0;
int[] dis={1, -1, 5};
int[] ch;
Queue<Integer> Q = new LinkedList<>();
public int BFS(int s, int e){
// 좌표 최대 범위만큼 배열의 크기를 잡는다. 0번 인덱스는 사용하지 않음
ch=new int[10001];
//출발지점 s에 대해 방문함을 체크
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<3; j++){
int nx=x+dis[j];
if(nx==e){
// 답은 반드시 존재하므로(문제조건) 무조건 여기서 return 된다.
// L은 x의 레벨값이므로 nx의 레벨값은 L+1
return L+1;
}
// nx>=1 && nx<=10000 : 좌표 범위 제한
if(nx>=1 && nx<=10000 && ch[nx]==0){
ch[nx]=1;
Q.offer(nx);
}
}
}
L++;
}
// 무조건 중간에서 return되지만 반환형이 int이므로 문법에러 방지를 위해 임의의 수 리턴
return 0;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int s=kb.nextInt();
int e=kb.nextInt();
System.out.println(T.BFS(s, e));
}
}
Author And Source
이 문제에 관하여([BFS] 8. 송아지 찾기1(BFS : 상태트리탐색)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jhjcoding/8.-송아지-찾기1BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)