알고리즘
백준 12761번 돌다리 (JAVA)
박카스마시며코딩
2023. 12. 21. 17:26
https://www.acmicpc.net/problem/12761
12761번: 돌다리
동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대
www.acmicpc.net
저는 BFS를 통해 문제를 풀었습니다.
BFS를 통해 시작점에서 목표지점까지 최단 거리를 찾아 문제를 해결하였습니다.
package BOJ.bfs;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_12761 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int result = cal(n,m,a,b);
System.out.println(result);
}
private static final int LIMIT = 100_000;
private static int cal(int start, int target, int a, int b) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
int time = 0;
int[] length = new int[]{1,a,b};
Set<Integer> visited = new HashSet<>();
while(!q.isEmpty()){
int size = q.size();
for(int s = 0 ; s < size ; s++){
int now = q.poll();
if(now == target){
return time;
}
for(int i = 0 ; i < length.length ; i++){
int next = now + length[i];
if(next >= 0 && next <= LIMIT && !visited.contains(next)){
visited.add(next);
q.offer(next);
}
next = now - length[i];
if(next >= 0 && next <= LIMIT && !visited.contains(next)){
visited.add(next);
q.offer(next);
}
if(i == 0){
continue;
}
next = now * length[i];
if(next >= 0 && next <= LIMIT && !visited.contains(next)){
visited.add(next);
q.offer(next);
}
}
}
time++;
}
return -1;
}
}