[백준] 13549번 숨바꼭질3 (Java)

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

 

숨바꼭질 문제는 1, 2, 4 모두 풀었는데 3만 풀지 않아서 이번에 풀어보았다. 수빈이가 동생을 가장 빨리 찾을 수 있는 시간을 구하는 문제였고, 1차원 공간이기에 100,000의 경우 BFS로 풀어도 괜찮겠다고 생각했다.

수빈이의 위치와 그때 소요된 시간을 저장하고자 Position 클래스를 선언하였고 Comparable를 정의하여 우선순위 큐에 들어갈 때 정렬되도록 하였다.

 

오답 코드

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

public class Main {
	static int N, K;
	static HashSet<Integer> visited;
	static int[] dir = new int[] { -1, 1, 2 };

	static class Position implements Comparable<Position> {
		int num;
		int time;

		public Position(int num, int time) {
			this.num = num;
			this.time = time;
		}

		@Override
		public int compareTo(Position other) {
			return this.time - other.time;
		}
	}

	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());

		if (N == K) {
			System.out.println(0);
			return;
		}

		PriorityQueue<Position> dq = new PriorityQueue<>();
		visited = new HashSet<>();
		dq.add(new Position(N, 0));
		visited.add(N);

		while (!dq.isEmpty()) {
			Position c = dq.poll();
			int current = c.num;
			int time = c.time;

			for (int d : dir) {
				int next = current;

				if (d == 2) {
					next *= d;

					if (next == K) {
						System.out.println(time);
						return;
					}

					if (!visited.contains(next) && next >= 0 && next < 100000) {
						visited.add(next);
						dq.add(new Position(next, time));
					}
				} else {
					next += d;

					if (next == K) {
						System.out.println(time + 1);
						return;
					}

					if (!visited.contains(next) && next >= 0 && next < 100000) {
						visited.add(next);
						dq.add(new Position(next, time + 1));
					}
				}

			}
		}

	}
}

 

틀린 이유는 next == K 일 때 바로 return하기 때문이다.

이 경우 우선순위 큐를 쓰는 의미가 사라진다. next는 for문 안에서 만들어진 새로운 데이터이기 때문에 우선순위 큐의 poll로 꺼낸 최솟값이 아니기 때문이다. 그렇기 때문에 current == K로 변경해 주어야 우선순위를 고려하게 된다.

 

---

정답 코드

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

public class Main {
	static int N, K;
	static int[] dir = new int[] { -1, 1, 2 };

	static class Position implements Comparable<Position> {
		int num;
		int time;

		public Position(int num, int time) {
			this.num = num;
			this.time = time;
		}

		@Override
		public int compareTo(Position other) {
			return this.time - other.time;
		}
	}

	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());

		if (N == K) {
			System.out.println(0);
			return;
		}

		PriorityQueue<Position> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[100001];
		pq.add(new Position(N, 0));

		while (!pq.isEmpty()) {
			Position c = pq.poll();
			int current = c.num;
			int time = c.time;

			if (visited[current]) continue;
			visited[current] = true;

			if (current == K) {
				System.out.println(time);
				return;
			}

			for (int d : dir) {
				int next = (d == 2) ? current * 2 : current + d;
				int nextTime = (d == 2) ? time : time + 1;

				if (next >= 0 && next <= 100000) {
					pq.add(new Position(next, nextTime));
				}
			}
		}

	}
}