[Java] 백준 / 숨바꼭질3 / 13549

[Java] 백준 / 숨바꼭질3 / 13549

문제

문제 링크

접근 방식

0부터 10만까지의 각 점은 자신의 위치로부터 -1과 1 에 해당하는 점으로 이동할 때의 가중치는 1이고 *2로 이동할 때의 가중치는 0이다. 따라서 모든 점에 대해 3개에 해당하는 인접리스트를 생성한다

그 후 다익스트라 알고리즘을 사용하여 수빈이의 위치에서 동생이 있는 위치까지의 최소 거리를 찾아 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_13549 {
	static int N,K;
	
	static class Vertex implements Comparable<Vertex>{
		int no;
		int w;
		
		Vertex(int no, int w){
			this.no = no;
			this.w = w;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.w - o.w;
		}
	
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Vertex>> list = new ArrayList<>();
		
		for(int i=0;i<=100000;i++) {
			list.add(new ArrayList<>());
			if(i-1 >= 0) list.get(i).add(new Vertex(i-1,1));
			if(i+1 <= 100000) list.get(i).add(new Vertex(i+1,1));
			if(i*2 <= 100000 && i!= 0) list.get(i).add(new Vertex(i*2,0));
		}
		
		int[] distance = new int[100001];
		boolean[] visited = new boolean[100001];
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		int start = N;
		
		distance[start] = 0;
		
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		pq.offer(new Vertex(start,0));
		
		while(!pq.isEmpty()) {
			int current = pq.poll().no;
			
			if(visited[current]) continue;
			visited[current] = true;
			
			if(current == K) {
				System.out.println(distance[current]);
				break;
			}
			
			for(Vertex v : list.get(current)) {
				
				if(distance[v.no]> distance[current] + v.w ) {
					distance[v.no]= distance[current] + v.w;
					pq.offer(new Vertex(v.no,distance[v.no]));
				}
			}
			
		}
		
	}

		
	
}