글 읽기 - 1753번 C++ 시간 초과 질문

sj4714 2년 전 1

안녕하세요 다익스트라 알고리즘을 공부하면서 문제 풀다가 계속 시간 초과가 발생하네요.

먼저 코드를 설명드린다면,

입력에서 arr[u].push_back({ v,w }); : u에서 v로 가는 가중치 w의 간선 추가

diks() 함수 안에서

- for (int i = 1; i <= V; i++) dist[i] = INF; dist[K] = 0; : 맨 처음엔 아직 연결정보를 모른다고 생각해 dist[]는 모두 INF로, 자기 자신은 0으로 초기화

- priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;

시작 노드(K 노드)에서 가장 가까운 노드와 최단거리(dist)를 저장하는 우선순위 큐

cmp로 비교함수를 만들었습니다. 큐에는 { 노드 번호, 최단 거리 } 가 저장되므로 최단 거리가 작은 것부터 오도록 했습니다.

-while{!q.empty()} 에서 먼저 q.top()으로 K에서 가까운 노드를 꺼냅니다.(이를 current 노드라 하겠습니다.)

current 노드와 연결된 노드(next_node) 및 그 노드의 최단거리 정보(dist_to_next_node)를 보고

만약 지금까지 갱신한 dist보다 ' current까지의 최단거리 + current에서 해당 노드까지 거리 ' 가 더 가깝다면 새로 갱신, q에 넣기

이후 q.top()은 K에서 가장 가까운 노드에 대한 정보( 노드 번호, 그 노드까지의 거리 )를 가지며 위 과정을 반복

제가 이해한 바로는 시작 지점에서 가장 가까운(dist가 가장 작은) 노드를 순차적으로 방문해 각 노드들로의 dist를 갱신한다 인 거 같고, 이를 토대로

구현했습니다. 근데 시간 초과가 뜨는 걸 봐선 제가 잘못 이해한 부분이 있거나 잘못 구현한 것 같은데, 어디가 문제인지 지적해 주시면 감사하겠습니다.

최대한 설명드리고자 글을 적었는데 글솜씨가 안 좋아서 내용이 이해가 안 되실 수도 있으실 것 같습니다.

이해가 안 되신다면 댓글 주시면 최대한 노력해서 다시 설명드리겠습니다.

이전에는 계속 '틀렸습니다' 였는데 이건 INF를 10으로 해서 그러네요... 혼선 빚어 죄송합니다

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 50000;

vector<pair<int, int>> arr[20001];
int dist[20001];
int V, E, K;

struct cmp
{
	bool operator()(const pair<int, int>& a, const pair<int, int>& b)
	{
		if (a.second != b.second)
			return a.second < b.second;
		else
			return a.first < b.first;
	}
};

void diks()
{
	for (int i = 1; i <= V; i++)
		dist[i] = INF;
	dist[K] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
	q.push({ K,0 });
	while (!q.empty())
	{
		int current = q.top().first;
		int distance = q.top().second;
		q.pop();
		for (int i = 0; i < arr[current].size(); i++)
		{
			int next_node = arr[current][i].first;
			int dist_to_next_node = arr[current][i].second;
			if (dist[next_node] > dist_to_next_node + distance)
			{
				dist[next_node] = dist_to_next_node + distance;
				q.push({ next_node, dist[next_node]});
			}
		}
	}
	for (int i = 1; i <= V; i++)
	{
		if (dist[i] == INF) cout << "INF" << endl;
		else cout << dist[i] << endl;
	}
}

int main()
{
	cin >> V >> E;
	cin >> K;
	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		arr[u].push_back({ v,w });
	}
	diks();
	return 0;
}

wnsduds1 2년 전 1

다익스트라에서 방문처리에 대해서는 여러가지 방법이 있는 것으로 알고있습니다 .우선 그러한 처리가 안되어있다는 점과

입력과 출력이 많아서 tle가 생길 수 있습니다/fastio에 대해 알아보시거나 scanf printf를 사용하시길 권장드립니다,

또한 cmp때문인지는 몰라도 같은로직에 상당히 느리기는하네요..

비교함수없이 pair클래스는 first기준으로 디폴트가되어있으니 first,second를 바꾸어서 제출도해보세요

wnsduds1 2년 전 1

INF도 int 형 범위내 굉장히 큰 수를 사용하시는 것을 추천합니다.. 987654321이라던가..

djm03178 2년 전 1

우선 endl은 너무 느리니 '\n'으로 바꾸어 주세요.

그리고 operator() 내의 비교 연산자가 잘못되었습니다. priority_queue는 기본적으로 더 큰 값부터 뽑아내기 때문에 20번째 줄에서도 <가 아닌 >를 사용해야 반대로 더 작은 값부터 뽑게 됩니다.

djm03178 2년 전 1

또한 윗분 말씀처럼 INF 값을 늘려야 하는데, 최단경로로 나올 수 있는 가장 먼 거리는 (정점의 수 - 1) * (간선의 최대 가중치)이므로 이 문제에서도 최소 20만 정도가 되어야 합니다.

마지막으로 https://www.acmicpc.net/proble... 를 참고해서 빠른 입출력을 하면 100ms까지 줄일 수 있습니다.

sj4714 2년 전 0

헉 두분 말씀하신거 전부 적용해서 바로 성공했습니다... 진짜 감사합니다.

wnsduds1님 : 그냥 cin,cout 쓰면 느리다고 듣기만 하고 항상 무시했는데...이번에 확실하게 느끼네요 fastIO 관련해서 알아두고 쓰겠습니다 도움 많이 됐습니다.

djm03178님 : 솔직히 cin, cout이 느린 건 알고 있었는데 endl은 몰랐네요... 그리고 연산자가 잘못된 것도 몰랐습니다. 저 부분을 제대로 공부 안 했던거 같습니다.

방금 검색해서 제가 이해한 바로는 cmp가 true면 swap을 한다는 것 같은데 맞나요? 바쁘시다면 답변 안 주셔도 괜찮습니다 ㅎㅎ..

제 실력이 부족해서 답변주셔도 이해 못 할 까봐 걱정했는데 쉽게들 가르쳐주셔서 바로 이해했습니다 답변주셔서 감사합니다.

true일 때 swap을 하는지 그런 건 내부 구현체를 잘 몰라서 모르겠지만, 그냥 priority_queue가 원래 max heap을 구현한 거라는 것만 생각하시면 됩니다. 제일 큰 수가 먼저 뽑히게 만들려면 반대로 compare 함수는 제일 작은 수가 제일 큰 수인 것처럼 속여서 알려줘야 제일 작은 수를 먼저 뽑아줄 것이기 때문에 () 연산자의 구현도 거꾸로 해줘야 하는 것입니다.

sj4714 2년 전 0

도움 많이 되었습니다 감사합니다 ㅜㅜ

nky212 2년 전 0

위 코드에서 혹시 우선순위 큐에서 타입을 그냥 정점으로 int로 안하고 꼭 pair<int, int>로 해야만 하나요? 어차피 정점만 넣어줘도 가중치는 그래프 정보를 담는 벡터에서 접근이 가능한데 꼭 왜 pair<int, int> 로 넣어야 하는지 궁금합니다. 다른 코드를 봐도 대부분 다 그렇게 넣네요 ㅜㅜ

djm03178 2년 전 0

우선순위 큐는 내부 상태가 힙의 조건을 만족하고 있지 않은 상태에서 삽입이나 삭제를 하면 문제가 생깁니다. 예를 들어 우선순위 큐에 정점 A를 처음 넣을 때는 가중치가 10이었는데 나중에 5로 바뀌는 바람에 다시 정점을 넣었다고 합시다. 그러면 우선순위 큐 내부에서 힙의 조정이 이루어져야 하는데 만일 우선순위 큐 안에 7이라는 가중치를 가진 정점 B가 들어있었다면 분명 처음에는 B가 A보다 가중치가 작았는데 재계산을 하니까 갑자기 A가 더 작다고 하니 우선순위 큐 입장에서는 혼란이 생깁니다. 힙 구조가 어느샌가 망가져 있었다는 뜻이기 때문입니다.

정점만 넣는 우선순위 큐를 구현할 수도 있습니다. 다만 이건 C++의 priority_queue로는 해결할 수 없고, set(이건 그 자체로 훨씬 느려서 의미가 없습니다)을 사용하거나 임의의 원소를 수정할 수 있는 우선순위 큐를 구현해야 합니다.

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

문제

문제

출처

ICPC

1753번 C++ 시간 초과 질문

sj4714 2년 전 1

wnsduds1 2년 전 1

wnsduds1 2년 전 1

djm03178 2년 전 1

djm03178 2년 전 1

sj4714 2년 전 0

djm03178 2년 전 1

sj4714 2년 전 0

nky212 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말