Coding Test/Baekjoon
백준 1326번 폴짝폴짝(Java)
good_da22
2022. 9. 6. 23:11
1326번 폴짝폴짝 (Java)
난이도
- Silver 2
알고리즘 분류
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
풀이
- 현재 위치에서 갈 수 있는 징검다리 선택
- 다음 징검다리 방문 여부 확인
- 방문이 안된 경우 방문 체크, 몇 번째 방문인지 기록
현재 위치 기준 배수만큼 이동 가능(좌우로 이동 가능)
코드
// 백준, 1326번, 폴짝폴짝, 실버2
// https://www.acmicpc.net/problem/1326
public class Main {
private static int N;
private static int start;
private static int end;
private static int[] arr;
private static int answer;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(in.readLine());
arr = new int[N + 1]; // 1번 인덱스 부터 사용
StringTokenizer st = new StringTokenizer(in.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(in.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
answer = -1;
bfs(start); // 너비 우선 탐색
sb.append(answer);
out.write(sb.toString());
out.close();
}
private static void bfs(int a) {
Queue<Integer> queue = new ArrayDeque<Integer>();
int[] cnt = new int[N + 1]; // 몇 번째 방문인지 기록
boolean[] visited = new boolean[N + 1]; // 방문여부
visited[a]= true;
queue.offer(a);
while (!queue.isEmpty()) {
int current = queue.poll();
if (visited[end]) {
answer = cnt[end];
return;
}
// 오른쪽 이동
for (int i = 1; i <= N; i++) {
int right = current + (arr[current] * i);
if(right > N) {
break;
}
if (!visited[right]) {
cnt[right] = cnt[current] + 1;
visited[right] = true;
queue.offer(right);
}
}
// 왼쪽 이동
for (int i = 1; i <= N; i++) {
int left = current - (arr[current] * i);
if(left < 1) {
break;
if (!visited[left]) {
cnt[left] = cnt[current] + 1;
visited[left] = true;
queue.offer(left);
}
}
}
}
}