https://www.acmicpc.net/problem/12851
import java.io.*;
import java.util.*;
public class Main
{
static int n;
static int m;
public static class Node{
int x;
int step;
public Node(int x, int step){
this.x=x;
this.step =step;
}
}
public static int[] bfs(Node start){
Queue<Node> q = new LinkedList();
boolean[] visited = new boolean[100_001];
int min_time=100_001;
int count=0;
q.offer(start);
while(q.size()>0){
Node node = q.poll();
if(node.step>min_time) break;
if(node.x==m){
min_time = node.step;
count++;
continue;
}
visited[node.x]=true;
int[] next= {node.x+1,node.x-1,node.x*2};
for(int i=0;i<3;i++){
if(next[i]<= 100_000 && next[i]>=0 && !visited[next[i]]){
q.offer(new Node(next[i],node.step+1));
}
}
}
return new int[]{min_time,count};
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input1 = br.readLine().split(" ");
n = Integer.parseInt(input1[0]);
m = Integer.parseInt(input1[1]);
int[] ans = bfs(new Node(n,0));
System.out.println(ans[0]);
System.out.println(ans[1]);
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Main {
static int n, k;
static int[] visited = new int[100001];
static int[] count = new int[100001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
Queue<Integer> q = new LinkedList<>();
q.add(n);
visited[n] = 1;
count[n] = 1;
while (!q.isEmpty()) {
int now = q.poll();
if (now == k) break;
int[] next = {now - 1, now + 1, now * 2};
for (int i = 0; i < 3; i++) {
if(!isRange(next[i])) continue;
if (visited[next[i]] == 0) {
visited[next[i]] = visited[now] + 1;
count[next[i]] = count[now];
q.add(next[i]);
} else if (visited[next[i]] == visited[now] + 1) {
count[next[i]] += count[now];
}
}
}
System.out.println(visited[k] - 1);
System.out.println(count[k]);
}
static boolean isRange(int x) {
return x >= 0 && x <= 100000;
}
}
'Problem Solving > BFS' 카테고리의 다른 글
BOJ7569 토마토 (0) | 2024.03.11 |
---|---|
BOJ7562 나이트의 이동 (0) | 2024.03.10 |
BOJ1697 숨바꼭질 (0) | 2024.03.10 |
BOJ2178미로탐색(최소이동구하기) (0) | 2024.03.10 |
BOJ2573 빙산* (1) | 2024.03.08 |