글 읽기 - dijkstra Priority queue로 처음 짜보는데 오답이 나네요.

orange4glace 8년 전 0

노드를 방문해서 거리를 갱신할때마다 pq에 노드를 넣어주고

pq에서 pop 할 때 해당 노드가 이미 방문된 노드면 continue 하도록 구현했습니다.

어디가 잘못된건지요?

지적부탁드립니다.

#include <cstdio>
#include <queue>
#include <stack>
#include <iostream>
using namespace std;

#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))

int N, M, K, Q, X, Y;

struct Point {
	int index;
	int cost;
};

int INF = 1 << 30;
vector< pair<int, int> > graph[20001];
int cost[20001];
bool visit[20001];
priority_queue<Point> pq;

bool operator<(const Point& a, const Point& b) {
	return a.cost > b.cost;
}

int main() {

	scanf("%d", &N);
	scanf("%d", &M);

	int x, y;
	scanf("%d", &x);

	for (int i = 1; i <= M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph[a].push_back(make_pair(b, c));
	}

	for (int i = 0; i < 20001; i++) cost[i] = INF;
	cost[x] = 0;
    visit[x] = true;
	Point firstP;
	firstP.index = x;
	firstP.cost = 0;
	pq.push(firstP);
	for (int i = 1; i <= N; i++) {
		int min = INF, minp = 0;
		while (!pq.empty()) {
			Point p = pq.top();
			min = p.cost;
			minp = p.index;
			pq.pop();
			if (visit[minp]) {
                minp = 0;
				continue;
            }
		}
		if (minp == 0) break;
		visit[minp] = true;
		for (int j = 0; j < graph[minp].size(); j++) {
			int next = graph[minp][j].first;
			if (cost[next] > cost[minp] + graph[minp][j].second) {
				cost[next] = cost[minp] + graph[minp][j].second;
				Point p;
				p.index = next;
				p.cost = cost[next];
				pq.push(p);
			}
		}

	}
	for (int i = 1; i <= N; i++) {
		if (cost[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", cost[i]);
	}
	cin >> N;


	return 0;
}

rlatkddn212 8년 전 1

아.. 윗분 말씀이 맞습니다. 너비우선 탐색하고 해깔렸네요.. 죄송합니다. 잘못된 답변은 지우겠습니다..

두분 모두 답변 감사합니다. 그런데 아직 이해가 잘 되지 않는게, 다익스트라가 현재 선택되지 않은 정점 중 최소값을 가진 정점을 선택해서 그 정점과 연결된 모든 정점과의 거리를 갱신하는것인데, 거리를 갱신할때마다 PQ에 값이 들어가게 되고, 뽑아낼 때 그 값이 이미 visit 됐는지 아닌지를 체크하면 되는것 아닌지요? 대소라 하면 어떤것과의 대소를 말씀하시는것인지요?

rlatkddn212 8년 전 1

우선 지금 코드는

0. 첫번째 시작정점을 우선순위 큐에 넣는다. 시작 정점 방문체크함

1. 정점의 수만큼 루프를 돌린다.

2. 우선 순위 큐에서 시작 정점의 값을 꺼낸다.

3. 시작정점이 방문된 상태이므로 루프를 빠져나온다.

4. 종료.

이렇게 되있는 것 같아요..

baactree 8년 전 2

for문은 N번 돌리는 방식으로 하는게 아니구요

우선순위큐에 (코스트합,도착정점)을 넣고

우선순위큐가 empty될때까지 반복

코스트 합이 최소인 곳을 방문 하고

지금까지 구한 코스트랑 현재 팝한 코스트랑 비교해서 현재 팝한게 더 크다면 의미 없기 때문에 컨틴뉴 하고

아니라면 지금 팝한 정점에서 연결된 모든 정점들에 대해서 (코스타합,도착정점)을 다시 우선순위 큐에 넣고

반복합니다

dist[정점크기]=무한대로 초기화;
dist[start]=0;
pq.push(0,start);
while(!pq.empty()){
    cost = -pq.top().first;
    now = pq.top().second;
    pq.pop();
    if(dist[now]<cost) continue;
    for(i=0;i<now.size();i++){
        다음정점;
        다음 코스트합;
        if(dist[다음정점]>다음 코스트합)
            pq.push(-다음코스트합,다음정점);
    }
return dist[finish];

rlatkddn212 8년 전 1

코드 파악하기가 힘들었지만...

고생해서 고쳐봤습니다.

생각보다 고칠 부분이 없더라구요..

변경점 :

1. while 문을 if 문으로 고침

수정전 while문에서 pq의 모든 노드를 제거해버리고 마지막 노드만 취하게 됩니다...

2. 정점의 개수만큼 반복하지 않고 간선의 개수 만큼 반복하도록 수정했습니다.

정점의 개수만큼만 돌면 모든 간선을 확인하지 못하므로 간선의 수만큼 돌렸습니다.

#include <cstdio>
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
 
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
 
int N, M, K, Q, X, Y;
 
struct Point {
    int index;
    int cost;
};
 
int INF = 1 << 30;
vector< pair<int, int> > graph[20001];
int cost[20001];
bool visit[20001];
priority_queue<Point> pq;
 
bool operator<(const Point& a, const Point& b) {
    return a.cost > b.cost;
}
 
int main() {
 
    scanf("%d", &N);
    scanf("%d", &M);
 
    int x, y;
    scanf("%d", &x);
 
    for (int i = 1; i <= M; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
    }
 
    for (int i = 0; i < 20001; i++) cost[i] = INF;
    cost[x] = 0;
    Point firstP;
    firstP.index = x;
    firstP.cost = 0;
    pq.push(firstP);
    for (int i = 1; i <= M; i++) { // 수정
        int min = INF, minp = 0;
        if (!pq.empty()) { // 수정
            Point p = pq.top();
            min = p.cost;
            minp = p.index;
            pq.pop();
            if (visit[minp]) {
                minp = 0;
                continue;
            }
        }
        if (minp == 0) break;
        visit[minp] = true;
        for (int j = 0; j < graph[minp].size(); j++) {
            int next = graph[minp][j].first;
            if (cost[next] > cost[minp] + graph[minp][j].second) {
                cost[next] = cost[minp] + graph[minp][j].second;
                Point p;
                p.index = next;
                p.cost = cost[next];
                pq.push(p);
            }
        }
 
    }
    for (int i = 1; i <= N; i++) {
        if (cost[i] == INF)
            printf("INF\n");
        else
            printf("%d\n", cost[i]);
    }
 
 
    return 0;
}

orange4glace 8년 전 0

두분다 답변 너무 열심히 해주셔서.. 감사합니다 !

말씀해주신것 다시 한번 생각해보면서 풀어보겠습니다 ㅜㅜ

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

문제

문제

출처

ICPC

dijkstra Priority queue로 처음 짜보는데 오답이 나네요.

orange4glace 8년 전 0

baactree 8년 전 2

rlatkddn212 8년 전 1

orange4glace 8년 전 0

rlatkddn212 8년 전 1

baactree 8년 전 2

rlatkddn212 8년 전 1

orange4glace 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말