글 읽기 - [C++] 60% 즈음에서 시간초과가 나는데 이유를 도저히 모르겠습니다 ㅠㅠ

kyj93790 2년 전 0

이미 올라와 있는 질문들을 읽었고, 다음과 같은 사항을 확인했습니다.

1. 우선 순위 큐를 활용하여 다음으로 탐색할 노드를 찾아야 한다.

이 부분에서 많은 분들이 부등호 방향으로 시간초과를 겪었음을 확인했고, node에 대해서는 작은 값이 top으로 올 수 있도록 구현했습니다.

2. endl, cin, cout으로 인한 시간 초과가 있을 수 있다.

'\n', ios::sync_with_studio(false)를 작성해줌으로써 이를 방지하였습니다.

3. 메모리 초과 또한 막기 위해 vector 배열을 생성하여 간선의 정보를 저장하였습니다.

4. 우선 순위 큐에 이전에 방문했던 node의 정보가 존재할 수 있는데, 이는 고려하지 않도록 했습니다.

이에 대한 구현은 필독 글에 따라 현재 distance 배열의 값과 일치하지 않는 경우 continue를 하도록 했습니다.

제가 추가적으로 고려해야 할 부분 중에 놓친 부분 말씀해주시면 감사하겠습니다 :)

#include <iostream>
#include <queue>
#define INF 200000
using namespace std;

typedef struct node {
	int v;
	int w;
	bool operator<(const node x) const {
		return this->w > x.w;
	}
}node;

int main(void) {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int V, E;
	cin >> V >> E;
	int K;
	cin >> K;
	vector<node> head[20001];	// 간선에 대한 정보
	priority_queue<node> pq;	// 미방문 최단 거리에 대한 정보
	int distance[20001];
	node x;
	for (int i = 1; i <= V; i++) distance[i] = INF;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		x.v = v;
		x.w = w;
		head[u].push_back(x);
		distance[v] = INF;
	}
	int c = V - 1;
	x.v = K;
	x.w = 0;
	distance[K] = 0;
	pq.push(x);
	while (c) {
		x = pq.top();
		pq.pop();
		if (x.w != distance[x.v]) continue;	// 구 버전의 최단 거리이므로 고려할 필요 없음.
		for (int i = 0; i < head[x.v].size(); i++) {    // 인접 노드 모두 탐색
			if (head[x.v][i].w + distance[x.v] < distance[head[x.v][i].v]) {	// 시작점->x->인접노드 vs 시작점->인접노드
				distance[head[x.v][i].v] = head[x.v][i].w + distance[x.v];
				node temp;
				temp.v = head[x.v][i].v;
				temp.w = distance[head[x.v][i].v];
				pq.push(temp);
			}
		}
		c--;
	}
	for (int i = 1; i <= V; i++) {
		if (distance[i] == INF) cout << "INF\n";
		else cout << distance[i] << '\n';
	}
	return 0;
}

ckdgus2482 2년 전 1

pq가 비워지면 while을 빠져나와야합니다.

출발지를 제외한 모든 정점이 한번 이상씩 우선순위 큐에 들어갔다가 나온다고 가정을 하신 것 같은데 그렇지 않습니다.

예를 들어 어떤 정점 하나가 다른 어떠한 정점과도 연결되지 않은 독립 컴포넌트라고한다면 우선순위 큐에는 그 정점으로 가는 경로의 정보가 들어갈 일이 없습니다.

즉 c가 0이 되기 전에 pq가 비워질 것입니다.

그래서 이미 필요한 모든 경로를 조사했음에도 불구하고 while을 빠져나오지 못하는 상태가 발생하는 것 같습니다.

kyj93790 2년 전 0

독립 컴포넌트를 고려하지 않아 문제가 발생한 것이었네요.

덕분에 문제 해결했습니다.

감사합니다 :)

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

문제

문제

출처

ICPC

[C++] 60% 즈음에서 시간초과가 나는데 이유를 도저히 모르겠습니다 ㅠㅠ

kyj93790 2년 전 0

ckdgus2482 2년 전 1

kyj93790 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말