[BOJ] 13549번: 숨바꼭질3
문제 (Gold 5)
풀이
처음에 단순히 BFS ( 1차원 배열 탐색 ) 으로 풀었더니 당연히! 시간초과가 났다.
그래서 방문하는 인덱스마다의 최단거리를 구하는 다익스트라 알고리즘 사용!
코드
더보기
package shortestPath;
import java.util.*;
import java.io.*;
public class Main_13549_숨바꼭질3{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
System.out.println(dijkstra(N, K));;
}
private static int dijkstra(int n, int k) {
PriorityQueue<int[]> q = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1[1], o2[1])));
int[] dist = new int[100001];
Arrays.fill(dist, Integer.MAX_VALUE);
q.offer(new int[]{n, 0});
dist[n] = 0;
while (!q.isEmpty()){
int[] cur = q.poll();
if(dist[cur[0]] < cur[1]) continue;
if(cur[0] == k){
break;
}
int[] ni = new int[]{cur[0]-1, cur[0]+1, cur[0]*2}; // 갈 수 있는 인덱스
for(int i =0 ; i < 3; i++){
if(0<=ni[i]&&ni[i]<100001){
int sec = (i == 0 || i == 1)? 1:0; // *2 는 순간이동이므로 시간이 추가되지 않음
if(dist[ni[i]] > dist[cur[0]] + sec){
q.offer(new int[]{ni[i], dist[cur[0]] + sec});
dist[ni[i]] = dist[cur[0]] + sec;
}
}
}
}
return dist[k];
}
}
제출
오래도 걸렸다,,,, 7트만에 성공!!!!!!!!
Author And Source
이 문제에 관하여([BOJ] 13549번: 숨바꼭질3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-13549번-숨바꼭질3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)