[BJ] 13549 : 숨바꼭질3

       문제 요약        

- 문제

 

 

- 입출력

 

         아이디어        

가장 빠른 시간을 찾아야 하기에 BFS를 생각했다

하지만, 2 * X 초의 경우 0초 후에 갈  수 있다고 해서 고민이 되었다 (가중치 다름)

 

 

now : 특정 위치에 도달할때까지 걸린 시간 이라는 것을 생각해보았다

만약 예전에 position에 도달한 적이 있고,

그때 걸린 시간이 더 짧다면 더 이상 이동하지 않음으로써 해결할 수 있음을 발견하였다

2번 : PQ 사용하는 방법

         소스코드        

[1] 다익스트라 알고리즘

package test;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

	static int N,K;
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		// 수빈이의 위치가 X , 걷는다면 X-1 or X+1로 이동, 순간이동 2*X
		System.out.println(dijkstra(N));
	}
	static int dijkstra(int start) {
		boolean[] visited = new boolean[100001];
		PriorityQueue<Item> queue = new PriorityQueue<>();
		queue.add(new Item(0,start));
		while(!queue.isEmpty()) {
			Item now = queue.poll(); // 비용이 가장 적은 걸 선택한다

			if(visited[now.position])continue; // 방문하지 않은 노드 중
			visited[now.position] = true;
			if(now.position==K) {
				return now.time;
			}
			if(now.position-1>=0 && now.position-1<=100000) {
				queue.add(new Item(now.time+1,now.position-1));				
			}
			if(now.position+1>=0 && now.position+1<=100000) {	
				queue.add(new Item(now.time+1,now.position+1));				
			}
			
			if(now.position*2>=0 && now.position*2<=100000) {
				queue.add(new Item(now.time ,now.position*2));				
			}
		}
		return Integer.MAX_VALUE;
	}
	static class Item implements Comparable<Item>{
		int time, position;
		Item(int time, int position){
			this.time = time;
			this.position = position;
		}
		@Override
		public String toString() {
			return "("+time+":"+position+")";
		}
		@Override
		public int compareTo(Item item) { // 비용이 가장 적은 걸 선택한다
			return this.time - item.time;
		}
	}
}

[2] 0-1 BFS

deque + bfs

가중치가 0또는 1일 때 사용

노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입

https://nicotina04.tistory.com/168

0-1 BFS(0-1 Breadth First Search)

[???] 왜 통과됩니까? (코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

	static int N,K;
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		// 수빈이의 위치가 X , 걷는다면 X-1 or X+1로 이동, 순간이동 2*X
		System.out.println(bfs(N));
	}
	static int bfs(int start) {
		int[] posTime = new int[100001];
		Arrays.fill(posTime, Integer.MAX_VALUE);
		Queue<Item> queue = new ArrayDeque<>();
		queue.add(new Item(0,start));
		while(!queue.isEmpty()) {
			Item now = queue.poll();

			if(now.time >= posTime[now.position])continue;
			posTime[now.position] = now.time; // 그 위치에 온다.
			if(now.position+1>=0 && now.position+1<=100000) {	
				queue.add(new Item(now.time+1,now.position+1));				
			}
			if(now.position-1>=0 && now.position-1<=100000) {
				queue.add(new Item(now.time+1,now.position-1));				
			}
			if(now.position*2>=0 && now.position*2<=100000) {
				queue.add(new Item(now.time ,now.position*2));				
			}
		}
		return posTime[K];
	}
	static class Item{
		int time, position;
		Item(int time, int position){
			this.time = time;
			this.position = position;
		}
		@Override
		public String toString() {
			return "("+time+":"+position+")";
		}
	}
}