[伯俊13913]鬼ごっこ4(Java)
質問する
https://www.acmicpc.net/problem/13913
に答える
BFSで解けました.
現在の数字をXと呼ぶ場合、QueueにX-1、X+1、2*Xを入れ、X=Kで印刷します.
この場合,パスも一緒に出力する必要があるため,prev配列を用いて以前の数字を格納する.
コード#コード#
https://www.acmicpc.net/problem/13913
に答える
BFSで解けました.
現在の数字をXと呼ぶ場合、QueueにX-1、X+1、2*Xを入れ、X=Kで印刷します.
この場合,パスも一緒に出力する必要があるため,prev配列を用いて以前の数字を格納する.
コード#コード#
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int K = scan.nextInt();
solution(N, K);
}
public static void solution(int N, int K) throws IOException {
int MAX_SIZE = 2*Math.max(N, K)+1;
int[] prev = new int[MAX_SIZE];
Arrays.fill(prev, -1);
prev[N] = -2; //-2 : 시작점을 표현
Queue<Integer> Q = new LinkedList();
Q.add(N);
boolean[] visited = new boolean[MAX_SIZE];
while(!Q.isEmpty()){
int cur = Q.poll();
if(visited[cur]) continue;
visited[cur] = true;
if(cur == K){
print(cur, prev);
return;
}
if(cur-1 >= 0 && prev[cur-1]==-1) {
Q.add(cur-1);
prev[cur-1] = cur;
}
if(cur+1 < MAX_SIZE && prev[cur+1]==-1) {
Q.add(cur+1);
prev[cur+1] = cur;
}
if(cur*2 < MAX_SIZE && prev[cur*2]==-1) {
Q.add(cur*2);
prev[cur*2] = cur;
}
}
}
public static void print(int cur, int[] prev) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tmp = cur;
int sec = 0;
List<Integer> outputList = new LinkedList();
while(tmp>=0){
outputList.add(tmp);
tmp = prev[tmp];
sec++;
}
bw.write((sec-1)+"\n");
for(int i=outputList.size()-1;i>=0;i--){
bw.write(outputList.get(i)+" ");
}
bw.close();
}
}
Reference
この問題について([伯俊13913]鬼ごっこ4(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@kjihye0340/백준-13913-숨바꼭질-4Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol