[백준 13549번][Java] 숨바꼭질 3 - 다익스트라(그래프 범위 설정)

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

다익스트라 알고리즘으로 풀기 전에 DP로 풀 수 있지 않을까? 라고 생각했지만 어렵겠다고 결론을 내렸습니다. 이유는 수빈이가 x-1로도 움직일 수 있기 때문입니다. 점화식은 구해지지만 이 경우 재귀로 풀어야 하는데 시간복잡도가 O(3^n)이 되므로 불가능합니다.

 

전형적인 다익스트라 알고리즘에 약간 추가로 생각해줘야 할 점이 있습니다. 그래프 노드의 범위를 정해주는 겁니다.

정해주지 않을 경우  x+1, x-1, 2*x  세 가지 연산으로 모든 정수를 만들 수 있기 때문에 무한 루프를 돌게 됩니다.

 

어떻게 범위를 정해줄 수 있을까요?

음... 해보진 않았지만 동생의 위치보다 적절히 큰 값을 대충 넣어줘도 될 것 같긴하지만 경계값을 찾아서 효율적인 알고리즘을 만들어 봅시다.

 

수빈이가 동생에게 도착하는 경우에는 두 가지가 있습니다.

 

1. + 방향으로 걸어서 도착하는 경우

2. 점프 후 - 로 걸어서 도착하는 경우

 

그래프의 최대 범위는 2번의 경우를 고려한 경계값이 됩니다.

점프해서 돌아오는 값이 의미가 있을려면 1번보다 2번이 더 빠를 경우입니다. 이를 부등식으로 계산하면  x의 범위가 정해집니다.

여기서 양변에 다시 2를 곱하면 그래프의 최대 경계값이 됩니다. 4*m/3 보다 작은 정수가 되겠네요.

 

참고 : 위의 경우는 수빈이가 동생보다 수직선상 왼쪽에 있을 경우에만 해당됩니다. 수빈이가 동생보다 오른쪽에 있는 경우엔 걸어가는 수 밖에 없으므로 거리의 차가 답이 됩니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
숨바꼭질 3
https://www.acmicpc.net/problem/13549
 */
public class Main {
	static int limit;
	static int[] spendTime;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
		StringTokenizer st = new StringTokenizer(reader.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		if(n >= m) {
			System.out.println(n-m);
			return;
		}
		limit = Math.floorDiv(4*m, 3);
		spendTime = new int[limit+1];
		Arrays.fill(spendTime, Integer.MAX_VALUE);

		daiijkstra(n, spendTime);
		System.out.println(spendTime[m]);
	}

	static int[] coefficient = {1,-1,2};
	private static void daiijkstra(int start, int[] spendTime) {
		PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparing(node -> node.time));
		q.add(new Node(start, 0));
		spendTime[start] = 0;

		while(!q.isEmpty()) {
			Node here = q.poll();
			if(here.time > spendTime[here.id]) continue;

			for (int i = 0; i < 3; i++) {
				int there = i != 2 ? here.id + coefficient[i] : here.id * coefficient[i];
				int nextTime = i != 2 ? here.time + 1 : here.time;
				if(isRange(there) && nextTime < spendTime[there]) {
					spendTime[there] = nextTime;
					q.add(new Node(there, nextTime));
				}
			}
		}
	}
	public static boolean isRange(int node) {
		if(node >= 0 && node <= limit) return true;
		return false;
	}

}
class Node {
	int id, time;
	public Node(int id, int time) {
		this.id = id;
		this.time = time;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}