[学習アルゴリズム]白駿11060
質問元:https://www.acmicpc.net/problem/11060
上記の問題を読むと、1 XNで形成された迷路を各位置で一定数移動することができます.各ロケーションに配列を作成した後、アクセス順を記録し、最後のロケーションの書き込み数が0の場合、最後のロケーションに到達できないと判断します.そうでない場合、BFSを使用して問題を解決します.最後のロケーションに到達すると、出力の最小ジャンプ回数が発生する可能性があります.
質問へのアクセス
上記の問題を読むと、1 XNで形成された迷路を各位置で一定数移動することができます.各ロケーションに配列を作成した後、アクセス順を記録し、最後のロケーションの書き込み数が0の場合、最後のロケーションに到達できないと判断します.そうでない場合、BFSを使用して問題を解決します.最後のロケーションに到達すると、出力の最小ジャンプ回数が発生する可能性があります.
ソースコード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] map = new int[N];
int[] check = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){ // 맵 생성
map[i] = Integer.parseInt(st.nextToken());
}
int index = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(map[index]);
while(!q.isEmpty()){
int y = q.poll(); // 큐에서 꺼내는 것
int visit = check[index]; // 이전 값 넣기
for(int i = 0; i < y; i++){
index++;
if(index >= N){
break;
}
if(check[index] == 0){
check[index] = visit + 1;
q.offer(map[index]);
}
}
if(y == 0){
index++;
}
for(int i = 0; i < y-1; i++){
index--;
}
}
if(N == 1){
System.out.println(0);
}
else if(check[N-1] == 0){
System.out.println(-1);
}
else{
System.out.println(check[N-1]);
}
}
}
Reference
この問題について([学習アルゴリズム]白駿11060), 我々は、より多くの情報をここで見つけました https://velog.io/@seokhwan-an/Algorithm-Study-백준-11060テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol