글 읽기 - 13549_숨바꼭질3 반례찾기, 도움 요청합니다

mangkoo 4년 전 0

우선순위 큐를 이용해 이동할 수 있는 가장 짧은 거리에서부터 탐색하도록 하였습니다.

대부분의 경우에 대해 답을 찾는 것 같은데 제출하면 틀렸다고 나오네요..

어디가 잘못된 것일까요

반례의 경우나 제가 틀린 부분이 있다면 알려주시면 감사하겠습니다! ㅠㅠ

package dfs_bfs;

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

public class Main_13549_숨바꼭질3 {
	static int N, K, tempNum;
	static boolean[] visited = new boolean[100001];
	static int max = 100000;

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

		bfs(new Pos(N, 0));

	}

	static void bfs(Pos before) {
		PriorityQueue<Pos> pq = new PriorityQueue<>();
		visited[before.num] = true;
		pq.offer(before);

		while (!pq.isEmpty()) {
			Pos tmp = pq.poll();
			tempNum = tmp.num;
			if (tempNum == K) {
				System.out.println(tmp.cnt);
				return;
			}

			if (tempNum * 2 >= 0 && tempNum * 2 <= max && !visited[tempNum * 2]) {
				visited[tempNum * 2] = true;
				pq.offer(new Pos(tempNum * 2, tmp.cnt));
			}
			
			if (tempNum - 1 >= 0 && tempNum - 1 <= max && !visited[tempNum - 1]) {
				visited[tempNum - 1] = true;
				pq.offer(new Pos(tempNum - 1, tmp.cnt + 1));
			}

			if (tempNum + 1 >= 0 && tempNum + 1 <= max && !visited[tempNum + 1]) {
				visited[tempNum + 1] = true;
				pq.offer(new Pos(tempNum + 1, tmp.cnt + 1));
			}
		}
	}

	static class Pos implements Comparable<Pos> {
		int num, cnt;

		public Pos(int num, int cnt) {
			super();
			this.num = num;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Pos o) {
			return this.cnt - o.cnt;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

13549_숨바꼭질3 반례찾기, 도움 요청합니다

mangkoo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말