글 읽기 - (100%, 1초)에서는 왜틀린걸까요...?

wony6731 4년 전 0

100%에서 틀렸습니다가 발생하였습니다.

예외처리를 안해준 것 같은데 제 눈에는 보이지가 않네요 ㅜㅜ

어떤 것이 있을까요...

우선순위 큐는 숨바꼭질3에 사용하였고, 그 코드를 그대로 사용하느라 우선순위큐를 사용하게 되었습니다.

/*
	Title : 숨바꼭질 3
	Description
		- X-1 or X+1 or 2*X
		- 수빈이가 동생 가장 빠르게 찾는 시간
	Solution
*/
#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int subin, target;
bool visited[100001];
int arr[100001];
vector<int>V;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int ,int>>> PQ;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> subin >> target;
	
	if (subin == target){
		cout << "0\n";
		cout << subin << "\n";
		return 0;
	}
	PQ.push(make_pair(0, subin));
	visited[subin] = true;
	while (!PQ.empty()){
		auto cur = PQ.top();
		PQ.pop();

		// 도착
		if (cur.second == target){
			cout << cur.first << "\n";
			
			V.push_back(cur.second);
			int idx = arr[cur.second];
			while (arr[idx] != 0){
				V.push_back(idx);
				idx = arr[idx];
			}
			V.push_back(idx);
			if (subin == 0)
				V.push_back(0);

			for (int i = V.size() - 1; i >= 0; i--)
				cout << V[i] << " ";
			cout << "\n";

			break;
		}

		int nx;

		// +1
		nx = cur.second + 1;
		if (nx <= 100000){
			if (!visited[nx]){
				PQ.push(make_pair(cur.first + 1, nx));
				visited[nx] = true;
				arr[nx] = cur.second;
			}
		}

		// -1
		nx = cur.second - 1;
		if (nx >= 0){
			if (!visited[nx]){
				PQ.push(make_pair(cur.first + 1, nx));
				visited[nx] = true;
				arr[nx] = cur.second;
			}
		}

		// x2
		nx = cur.second * 2;
		if (nx <= 100000){
			if (!visited[nx]){
				PQ.push(make_pair(cur.first + 1, nx));
				visited[nx] = true;
				arr[nx] = cur.second;
			}
		}
	}
	return 0;
}

omh9876 2년 전 0

저도 마찬가지로 100프로에서 틀립니다.. 혹시 해결하셨나요?

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

문제

문제

출처

ICPC

(100%, 1초)에서는 왜틀린걸까요...?

wony6731 4년 전 0

omh9876 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말