글 읽기 - 다른 분이 짜신 코드와 차이점이 뭔지 모르겠습니다.

yw9594 3년 전 0

하도 문제가 안풀려서 왜 틀렸는지 찾아보고 보완했음에도 불구하고 오류가 발생해 질문 드립니다.

위치 간 간선의 가중치가 다름을 고려해 우선 순위 큐를 사용해 해결했습니다.

특히 순간이동과 걷기의 가중치가 다르므로 배열을 사용해 다음 이동해야할 위치 중 순간이동을 먼저 큐에 삽입해주었습니다.

암만 봐도 다른 문제를 통과하신 분들의 코드와 다른 점이 없는 것 같은데.. 무엇이 문제일까요?

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Elem {
	int i, c; // 위치, 시간
	bool operator<(const Elem & arg) const {
		return this->c > arg.c; // minimum heap
	}
};

int check_range(int i) {
	if (i < 0 || i> 100000) return 0;
	else return 1;
}

int main(void) {
	std::istream::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K, answer;
	cin >> N >> K;

	priority_queue<Elem> pq;
	vector<int> pushed(100001, 0);
	
	pq.push({ N, 0 });
	pushed[N] = 1;

	while (!pq.empty()) {
		Elem c_e = pq.top();
		pq.pop();
		
		// 동생을 찾았을 경우
		if (c_e.i == K) {
			answer = c_e.c;
			break;
		}

		// 다음 노드 입력
		int n_i[] = { c_e.i * 2 , c_e.i + 1, c_e.i - 1}; // 반드시 순간이동부터 큐에 삽입한다.
		int n_c[] = { c_e.c, c_e.c + 1, c_e.c + 1 };

		for (int k = 0; k < 3; k++) {
			if (check_range(n_i[k]) && !pushed[n_i[k]]) {
				pq.push({ n_i[k], n_c[k] });
				pushed[n_i[k]] = 1;
			}
		}	
	}
	cout << answer <<"\n";

	return 0;
}

djm03178 3년 전 2

이 코드는 기본적으로 다익스트라를 하고 있는 것이기 때문에, 50번째 줄처럼 큐에 삽입할 때 바로 방문 표시를 하면 안 됩니다. 특정 지점에 큐에서 더 늦게 나온 정점으로부터 도달하는 것이 더 빠를 수도 있기 때문입니다. 다익스트라에서는 큐에서 뺀 뒤에 방문 표시를 해야 합니다.

예를 들어 우선순위 큐에 7과 3이 같은 시간 x초에 들어가있고 7이 먼저 큐에서 빠졌다면 7이 먼저 6을 x+1초에 방문할 텐데 실제로는 더 나중에 나온 3으로부터 6에 도달하면 x초만에 갈 수 있게 됩니다.

djm03178 3년 전 1

그리고 이 코드가 다익스트라이기 때문에 44번째 줄의 주석과 같이 반드시 어떤 정점을 먼저 큐에 넣으려고 할 필요는 없습니다.

yw9594 3년 전 0

와.. 똑부러지는 설명 감사드립니다. 바로 이해했습니다..!!

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

문제

문제

출처

ICPC

다른 분이 짜신 코드와 차이점이 뭔지 모르겠습니다.

yw9594 3년 전 0

djm03178 3년 전 2

djm03178 3년 전 1

yw9594 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말