글 읽기 - 다익스트라로 풀 경우 방문한곳 체크를 왜 하면 안되나요?

spring2 3년 전 1

//로 되어있는곳(25, 26번째 줄)을 // 처리해서 제출하니 바로 통과했는데 이유를 모르겠습니다.

애초에 25,26번째 줄이 있으나 없으나 우선순위 큐를 사용하기 때문에 왔던곳에 다시 계산할 일이 안생길꺼같은데..

왜이런거죠??

https://www.acmicpc.net/source...

다른 문제 비슷한 문제의 이 소스를 참고하여 풀었는데 문제의 어떤점이 달라서 check를 사용하면 안되는지 모르겠어요 ㅜㅜ.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int ind[801];
int dist[801];
//bool check[801];
const int INF = 1000000000;
int n, m;

void go(int start,vector<vector<pair<int,int>>>&v) {
    //memset(check,false,sizeof(check));
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
	q.push(make_pair(0, start));
	dist[start] = 0;
	while (!q.empty()) {
		int fx = q.top().second;
		int fc = q.top().first;
		q.pop();
		//if (check[fx])	continue;
		//check[fx] = true;
		for (int i = 0; i < v[fx].size(); i++) {
			int nx = v[fx][i].second;
			int cost = v[fx][i].first;
			if (dist[nx] > dist[fx] + cost)	{
                dist[nx] = dist[fx] + cost;
			    q.push(make_pair(cost, nx));
            }
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vector<vector<pair<int, int>>>v(n + 1, vector<pair<int, int>>());
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back(make_pair(z, y));
        v[y].push_back(make_pair(z, x));
	}
	int node1, node2;
	cin >> node1 >> node2;
	go(1, v);
	int onetonode1 = dist[node1];
	int onetonode2 = dist[node2];
	go(node1, v);
	int node1to2 = dist[node2];
	int node1ton = dist[n];
	go(node2, v);
	int node2to1 = dist[node1];
	int node2ton = dist[n];
	int ans1 = INF, ans2 = INF;
	if(onetonode1!=INF && node1to2!=INF && node2ton!=INF)
		ans1 = onetonode1 + node1to2 + node2ton;
	if(onetonode2!=INF&& node2to1!=INF && node1ton!=INF)
		ans2 = onetonode2 + node2to1 + node1ton;
	int ans = min(ans1, ans2);
	if (ans == INF)	cout << -1 << '\n';
	else cout << ans << '\n';
	return 0;
}

krgeo 3년 전 1

다익스트라 같은경우는 최소값 갱신해주는건데
1->2->3 비용이 10인데
1->4->3 비용이 5면 갱신되야대는데 check배열 쓰면 이게 안되지않나요??

spring2 3년 전 0

우선순위큐를 사용하기때문에 이미 최소값부터 계산되기때문에 check쓰나 안쓰나 뒤에 들어오는 큐들은 무시하면 되는거 아닌가요? ㅜㅜ

krgeo 3년 전 1

그림으로 다시 설명드리면. 최소비용을 선택한다고 해서 그게 최적의 값이 되는건 아닙니다.

다익스트라에서 우선순위큐를 사용하는 이유는 갱신비용의 감소가 큽니다.

이 그림 같은 경우 탐색 순서가 1->2->4->3->3이 되면서 마지막에 갱신이 돼야합니다..

if (dist[nx] > dist[fx] + cost) {
dist[nx] = dist[fx] + cost;
q.push(make_pair(cost, nx));
}

이것을 체크했다고 안하는게 아니라
동일한 노드에 대해서 그 노드의 간선을 ( 위 그림같은 경우는 3이 되겠네요) 다시 탐색하지 않는것인데요..
(이미 그 노드는 최소인 상태로 다른노드를 탐색했을테니)

실제로 큐를 이용하지 않고 다익스트라 구현할때,

for (int i = 1; i <= n; i++) {
  dist[i] = INF;
}
  dist[start] = 0;
for (int k = 0; k < n - 1; k++) {
  int m = INF + 1;
  int x = -1;
  for (int i = 1; i <= n; i++) { // node 선택
if (dist[i] < m && check[i] == false) {
m = dist[i];
x = i;
}
  }
  check[x] = true;
  for (int i = 0; i < v[x].size(); i++) {
  int next = v[x][i].first;
  int cost = v[x][i].second;
  if (dist[next] > dist[x] + cost) dist[next] = dist[x] + cost;
}
}

이부분에서 check써서 node 선택하는것이랑 제코드랑 다를바가 없다고 생각했거든요.

무슨차이가 있는지 이해가 안가서요 ㅜ

spring2 3년 전 2

제가 큐에 잘못넣었네요. 이미 최소인 상태로 넣었다고 생각했는데

그렇게 되려면

q.push(make_pair(dist[nx], nx));

했어야 했는데

q.push(make_pair(cost, nx)); 해버렸네요.

수정해서 제출하니 맞군요 ㅜ 해결되었습니다!

답변 감사합니다!

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

문제

문제

출처

ICPC

다익스트라로 풀 경우 방문한곳 체크를 왜 하면 안되나요?

spring2 3년 전 1

krgeo 3년 전 1

spring2 3년 전 0

krgeo 3년 전 1

spring2 3년 전 0

spring2 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말