[Silver II] 폴짝폴짝 - 1326
성능 요약
메모리: 13804 KB, 시간: 128 ms
분류
너비 우선 탐색, 그래프 이론, 그래프 탐색
제출 일자
2024년 1월 24일 20:54:46
문제 설명
개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.
이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.
입력
첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다.
접근 방법
1. 해당 인덱스를 가야한다. start가 큰지 End가 큰지 알 수 없다 그러므로 앞으로 가는 경우, 뒤로가는 경우 두가지를 봐야 함
2. 개구리 클래스를 만들고 위치와 점프한 횟수를 가지고 있다.
3. 방문 배열을 통해서 먼저 방문한 값이 최소값이기 때문에 반복해서 방문하지 않도록 한다.
4. bfs반복문이 끝나도 못찾는다면 -1을 리턴한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
// 개구리 클래스
static class Frog{
// 위치
int pos;
// 점프한 횟수
int count;
// 생성자
public Frog(int pos, int count) {
this.pos = pos;
this.count = count;
}
}
// 다리의 길이
static int n;
// 점프 할 값이 쓰여있는 징검다리 수
static int[] bridge;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
// 징검다리 배열 초기화
bridge = new int[n + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
// 각 수 입력
bridge[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
// 시작지점과 도착지점 입력 받음
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
System.out.println(bfs(start, end));
}
private static int bfs(int start, int end) {
// 방문 처리를 위한 배열 생성
boolean[] visit = new boolean[n + 1];
// 시작 지점 방문 처리
visit[start] = true;
// 각 개구리의 상태를 저장하기 위한 큐
Queue<Frog> queue = new LinkedList<>();
queue.offer(new Frog(start, 0));
while (!queue.isEmpty()) {
Frog cur = queue.poll();
// 위치가 도착지점이라면 바로 리턴
if(cur.pos == end){
return cur.count;
}
// 현재 위치에서 주어지는 정수의 배수만큼 갈 수 있음
int jump = bridge[cur.pos];
// 뒤로 가는 경우
for (int i = cur.pos; i >= 1; i -= jump) {
// 방문한 곳이라면 continue;
if (visit[i]) continue;
// 방문 처리
visit[i] = true;
queue.offer(new Frog(i, cur.count + 1));
}
// 앞으로 가는 경우
for (int i = cur.pos; i <= n; i += jump) {
// 방문한 곳이라면 넘어간다.
if(visit[i]) continue;
visit[i] = true;
queue.offer(new Frog(i, cur.count + 1));
}
}
return -1;
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 14716번 : 현수막 Silver1(실버1) - JAVA[자바] (1) | 2024.01.29 |
---|---|
[백준] 1309번 : 동물원 Silver1(실버1) - JAVA[자바] (1) | 2024.01.28 |
[백준] 1389번 : 케빈 베이컨의 6단계 법칙 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |
[백준] 11403번 : 경로 찾기 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |
[백준] 14675번 : 단절점과 단절선 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |