백준 12851번 숨바꼭질2 Java

문제로 이동

숨바꼭질2 문제

이전에 올린 숨바꼭질3와 유사한 문제인데, 이번 문제에선 순간이동 (현재 위치에서 *2로 이동하는 경우)이 1초가 걸린단 점, 목적지까지 가는데 최소시간과 가는 경우의 수를 모두 출력한다는 점이 다르다.

풀이

출발점에서 시작하여 +1, -1, *2 경우를 도착한 시간을 기준으로 priority queue에 추가한다. 이때 시간 초과, 메모리 초과가 나지 않도록 visited 배열을 통해 중복을 피하도록 해야한다. 초반 가능한 경우부터 살펴가는 방법이므로 BFS 알고리즘이라 볼 수 있다.

이때 중요하게 생각할 점은 이번 문제에선 도착지로 가는 최소시간의 모든 경우의 수를 구한다는 점이다. 그래서 중복을 피할 때, 만약 방문한 노드지만 걸린 시간이 더 작거나 같다면 queue에 넣어야한다. 이때 걸린 시간이 예전 방문했을 때보다 더 작은 경우는 priority queue를 이용했기 때문에 제외해서 생각해도된다.

코드

import java.util.*;
import java.io.*;

class Info implements Comparable<Info>{
	int location;
	int time;
	public Info(int location, int time) {
		this.location = location;
		this.time = time;
	}
	
	@Override
	public int compareTo(Info info) {
		return time - info.time;
	}
}

public class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	public static int[][] visited;
	static int answerCount = 0;
	static int arriveTime = 0;

	public static void main(String[] args) throws Exception{
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		visited = new int[1000000][2];
		move(n,k);
		System.out.println(arriveTime);
		System.out.println(answerCount);
	}
	
	public static int move(int start, int end) {
		PriorityQueue<Info> queue = new PriorityQueue<>();
		Info info = new Info(start, 0);
		queue.add(info);
		//목표에 도착했는지 확인하는 변수
		int flag = 0;
		while(!queue.isEmpty()) {
			Info cur = queue.poll();
			if(visited[cur.location][0] == 0 || cur.location == end || visited[cur.location][1] >= cur.time) {
				visited[cur.location][0] = 1;
				visited[cur.location][1] = cur.time;
				if(cur.location == end) {
					if(flag != 1) {
						flag = 1;
						arriveTime = cur.time;
						answerCount += 1;
						continue;
					}
					if(arriveTime == cur.time) {
						answerCount += 1;
					}
				}
				if(flag != 1) {
					if(cur.location + 1 <= 100000) {
						queue.add(new Info(cur.location + 1, cur.time + 1));
					}
					if(cur.location - 1 >= 0) {
						queue.add(new Info(cur.location - 1, cur.time + 1));
					}
					if(cur.location * 2 <= 100000) {
						queue.add(new Info(cur.location * 2, cur.time + 1));
					}
				}
			}
		}
		return arriveTime;
	}
}