13549 : 숨바꼭질 3 - JAVA

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

일반 숨바꼭질 문제에 비해 순간이동을 할 경우 코스트를 주지 않게 설정해서 조금 더 어렵게 설정한 문제이다.

 

당연히 너비 우선 탐색이라고 생각했고, 그것을 통해 2배 이동할지, 1-1 이동할지 정해서 계속 반복시켜서 목적지에 도착하도록 해야 한다.

 

나는 이 문제에서 가중치에 따른 우선 순위 큐를 어떻게 쓰는지 몰라서 헤멘 문제이다. 숨바꼭질과 똑같이 풀다가 틀렸다.

 

import java.util.*;

public class Main{
	static int n, k, sec;
	static boolean[] visit;
	static PriorityQueue<Point1> q;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		visit = new boolean[100001];
		q = new PriorityQueue<>();
		bfs(n);
		System.out.println(sec);
	}
	public static void bfs(int s) {
		q.add(new Point1(s, 0));
		while(!q.isEmpty()) {
			Point1 p = q.poll();
			visit[p.locate] = true;
			
			if(p.locate == k) {
				sec = p.depth;
				break;
			}
			if(p.locate * 2 <= 100000 && !visit[p.locate * 2]) {
				q.add(new Point1(p.locate * 2, p.depth));
			}
			if(p.locate + 1 <= 100000 && !visit[p.locate + 1]) {
				q.add(new Point1(p.locate + 1, p.depth + 1));
			}
			if(p.locate - 1 >= 0 && !visit[p.locate - 1]) {
				q.add(new Point1(p.locate - 1, p.depth +1));
			}
		}
	}
}
//우선순위 큐를 사용해야하는지 몰라서 해멘 문제
//레퍼런스를 참고하여 보충함
class Point1 implements Comparable<Point1>{
	int depth;
	int locate;
	Point1(int locate, int depth){
		this.depth = depth;
		this.locate = locate;
	}
	@Override
	public int compareTo(Point1 o) {
		// TODO Auto-generated method stub
		return depth - o.depth;
	}
}

 

우선순위 큐를 모른 채로 윗 방법대로 했다가 오답이 나서 변수에 -1을 주고 부등호 방향을 바꿔서 좀 꼬인 문제이다.

테스트 케이스는 제법 통과하길래 맞은줄 알았더니 완전 틀렸다. 

 

오답

 

import java.util.*;

public class Main{
	static int n, k, sec;
	static int[] field;
	static boolean[] visit;
	static Queue<Integer> q;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		field = new int[100000001]; 
		visit = new boolean[100000001];
		for(int i = 1; i <= 100000000; i++) {
			field[i] = i;
		}
		sec = 0;
		q = new LinkedList<>();
		bfs(n);
	}
	public static void bfs(int s) {
		q.add(s);
		while(!q.isEmpty()) {
			int location = q.poll();
			if(!visit[location])
				visit[location] = true;
			
				if(location == k) {
					System.out.println(sec);
					break;
				}
				else {
					if((location-1) * 2 <= k) {
						q.add(location*2);
					}
					else if(location * 2 > k) {
						if(Math.abs((location-1) * 2 - k) > Math.abs((location+1) * 2 - k)) {
							q.add(location+1);
							sec++;
						}
						else {
							q.add(location-1);
							sec++;
						}
					}
				}
		}
	}
}