코딩테스트 및 알고리즘
BFS 응용
영카이브
2024. 2. 24. 23:24
문제.
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.
현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.
송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.
최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
입력 예시
5 14
답 : 3
나의 답변
public class Main {
int[] dis = {-1,1,5};
int[] ck;
public int BFS(int s, int e) {
ck = new int[10001];
ck[s] = 1;
Queue<Integer> q = new LinkedList<>();
q.offer(s);
int lev=0;
while(!q.isEmpty()) {
int len = q.size();
// 해당 레벨 for문 돌기
for(int i=0; i<len; i++) {
// 큐에서 좌표 꺼냄
int x = q.poll();
// 한 좌표당 앞으로 1, 뒤로 -1, 앞으로 5 즉 3가지 경우가 있다.
for(int j=0; j<3; j++) {
// 해당좌표에 경우의 수 더함
int nx = x+dis[j];
// 그 레벨이 거리값과 같다. 그래서 송아지좌표와 같다면 lev에 +1을 하여 리턴
if(nx==e) return lev+1;
// 좌표의 범위가 1~100000이므로 이것 지킴
// 그리고 해당 좌표(nx)가 아직 방문되지 않았을 때 큐에 추가
if(nx >=1 && nx<=10000 && ck[nx]==0) {
ck[nx]=1;
q.offer(nx);
}
}
}
lev++;
}
return 0;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
// 현수 위치
int s = sc.nextInt();
// 송아지 위치
int e = sc.nextInt();
System.out.println(T.BFS(s,e));
}
}최단 경로는 BFS를 사용해서 푼다!!!!