글 읽기 - 30%에서 틀렸습니다가 뜨네요.

noxnia 4년 전 0

일단, 다익스트라 알고리즘을 그대로 이용하기는 했고요.

프리어리티 큐는 힙을 이용해서 구현했습니다.

그 외에 중복 처리를 위해서 unordered_map을 이용했고, 이걸로 인접리스트도 동시에 처리했습니다.

질문 게시판에 있는 데이터 갯수 최대로 잡은 것도 비교를 했는데, 결과가 같았는데요.

무언가 잘못한 것 같은데, 도저히 모르겠네요.

#include <stdio.h>
#include <unordered_map>
#include <algorithm>
#define	INF	1000000

int node[20000];
int readint() {int s; scanf("%d",&s); return s; }
int MIN(int a, int b) { return a<b?a:b; }
bool cmp(int a, int b) { return node[a] > node[b]; }
//bool cmp(int a, int b) { return a > b; }
int main()
{
	int heap[300000], hp=0;
	static char v[20000];
	std::unordered_map<int,int> edge[20000];
	int n=readint(), m=readint(), s=readint()-1;
	for(int i=0;i<n;i++) node[i]=INF;
	while(m--)
	{
		int u=readint()-1, v=readint()-1, w=readint();
		edge[u][v]=(edge[u].find(v)!=edge[u].end())?MIN(edge[u][v],w):w;
	}
	heap[hp++]=s; node[s]=0;
	while(hp)
	{
		std::pop_heap(heap,heap+hp--,cmp);
		int s = heap[hp]; if(v[s]) continue;
        v[s]=1;
		for(auto k : edge[s])
		{
			if(v[k.first]) continue;
			if(node[k.first] <= node[s]+k.second) continue;
			node[k.first]=node[s]+k.second;
			heap[hp++]=k.first;
			std::push_heap(heap, heap+hp, cmp);
		}
	}
	for(int i=0;i<n;i++) if(node[i]==INF) puts("INF"); else printf("%d\n", node[i]);
}

wjsqjawns 4년 전 0

방문 여부를 고려하지 않으시면 정답 처리가 됩니다.

noxnia 4년 전 0

방문여부는 검사를 안 해도 아무 상관없습니다. 다익스트라 알고리즘 자체상, 최솟값을 보장하기 때문에, 방문 검사를 하든 안 하든, 저 부분에서 영향을 미칠 일은 없어보입니다.

wjsqjawns 4년 전 0

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

위의 코드에서 방문 여부를 확인하지 않은 코드입니다.

wjsqjawns 4년 전 0

방문 여부를 확인하게 되면, 이후에 갱신되는 최솟값에 대한 갱신을 하지 않게 됩니다.

noxnia 4년 전 0

다익스트라 알고리즘에서 방문을 검사하는 것은 큰 의미가 없습니다. 어차피 그 다음에 최솟값 비교에서 통과를 안 할테니까요. 전, 통상적으로 BFS 하듯이 넣긴 하지만...

방문 여부 확인하지 않더라도, 음의 가중치가 없는 이상 절대 방문검사나 검사하지 않거나 관계없습니다.

방문한 노드 순서를 \(n_0, n_1, n_2, ..\) 이라고 할 때, 노드값을 \(N(n_0), N(n_1), ...\) 이라고 한다면,

뒤에 방문한 노드값이 이전 방문 노드값보다 작아지는 \(N(n_b) < N(n_a)\) 인 (b > a) 경우가 있다고 하자. 그렇지 않다면, 이미 방문한 노드의 노드값이 더 작아질 수 없습니다.

nb 업데이트를 하게 만든 노드는 이전에 방문한 노드들중 하나다. na 은 절대 nb 를 업데이트한 노드가 아니다.

na 이전 방문한 노드들 중 하나였다면, na가 선택될 때, nb가 선택되었어야 맞다.

na 이후의 노드에 의해서 바뀐것이라면, na 이후의 노드값은 na의 노드값보다 크기 때문에 nb 값을 na 값보다 작게 만들 수 없다.

수학 논리에 약해서..

jh05013 4년 전 2

cmp 함수가 node 값을 비교하고 있어서, node 값을 바꾸는 순간 heap은 더 이상 힙이 아니게 됩니다. 그래서 정점이 거리 순서대로 뽑힌다는 보장이 없습니다. heap 내부에 {거리, 번호} 순서쌍을 넣어 놓음으로써 heap 내부에서 비교를 해야 합니다.

wjsqjawns 4년 전 1

아, 그렇네요.

방문 여부의 갱신이 이뤄지는 위치를 잘못 봤네요, 죄송합니다.

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

(위의 코드에서 priority_queue를 사용한 정답 코드)

확인해보니, 힙이 문제였습니다.

djm03178 4년 전 1

@noxnia 다익스트라에서 방문 체크는 매우 중요합니다. 정답은 잘 나오지만, 시간이 문제입니다. http://www.secmem.org/blog/201...

djm03178 4년 전 0

다만 이 문제에서는 간선의 가중치가 범위가 작아서 저격이 될 정도의 데이터를 만들 수 없습니다.

noxnia 4년 전 0

@jh05013 고맙습니다. 저도 무심코 node[] 를 참조해서 cmp 함수를 만들었는데, 그것이 힙을 파괴한 것을 발견하고 고쳐서 AC 통과를 했습니다.

@djm03178 pop() 후에 방문체크는 꼭 해야 하지만, 인접리스트를 통한 방문체크는 안 해도 그 다음에 노드값 비교에서 걸러지게 됩니다. 딱히 시간 문제는 생기지 않을거라고 판단됩니다. 가중치값의 범위가 더 커지더라도 저격 데이터는 안 나오지 않을까 합니다.

djm03178 4년 전 1

pop 후의 방문 체크에 대해서만 말한 것이었는데, 대화의 요지는 그쪽이 아니었나 보군요.

noxnia 4년 전 0

네.. 인접리스트 검사에서의 문제였던 것으로 이해했었습니다. wjsqjawns 님이 노드값 업데이트 할 수 없다는 이야기로 보아서, 인접리스트 처리과정이라고 이해했었어요.

wjsqjawns 님이 링크 준 곳은 제가 확인을 안 해봐서요.

방문을 했음에도, 다시 큐로부터 방문한 노드를 가져와서 인접리스트를 검색했다면, 시간초과 가능성이 커질 듯 합니다.

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