글 읽기 - 50퍼센트에서 틀리네요 반례가 있는걸까요 아니면 애초에 풀이방향을 잘못잡은걸까요?

juhongkim2 6년 전 0

음수간선이 존재하기 때문에 벨만-포드 알고리즘을 사용했습니다

그래프를 어떻게 만들어야 하나...하고 고민하다가 다음처럼 그래프를 만들었습니다.

문제의 예시로 보여드리자면(S시작 E도착 G묘지 H구멍 0빈칸)

W=4, H=3일때

S 0 0 H

0 0 G G

0 0 0 E

에서 그리드의 각 칸을 노드로 생각하고 왼쪽 위부터 오른쪽 아래까지 1부터 W*H까지 번호를 매겼습니다.

이렇게 그래프를 만들고....(심각한듯)

벨만 포드 알고리즘을 써서 최단거리(dist[W*H])를 구해줬습니다.

만약 음수사이클이 생긴다면 Never를

dist[W*H]==INF라면 Impossible을

나머지 경우에는 해당 최단거리를 출력하도록 했습니다

그런데 50퍼쯤에서 틀리는데 어떤반례가 있을까요...

아니면 제가 애초에 문제푸는 방향을 잘못 잡은걸까요?

#include <stdio.h>
#include <algorithm>
#define INF 1000000000
using namespace std;

typedef struct{
	int from,to,cost;
}Edge;

bool operator<(Edge e1, Edge e2)
{
	if(e1.from<e2.from)
		return true;

	return false;
}

int W,H,G,E,grave[31*31],hole[31*31],dist[31*31];

Edge e[31*31*31];

int main()
{
	int i,j,ecnt,x,y,x2,y2,t,negative_cycle;
	Edge out;

	while(1){
		scanf("%d %d",&W, &H);

		if(W==0)
			break;

		ecnt=0;
		for(i=1;i<=W*H;i++){
			grave[i]=hole[i]=0;
			dist[i]=INF;
		}

		scanf("%d",&G);

		for(i=0;i<G;i++){
			scanf("%d %d",&x, &y);

			grave[y*W+x+1]=1;
		}

		scanf("%d",&E);

		for(i=0;i<E;i++){
			scanf("%d %d %d %d %d",&x, &y, &x2, &y2, &t);

			hole[y*W+x+1]=1;
			e[ecnt].from=y*W+x+1;
			e[ecnt].to=y2*W+x2+1;
			e[ecnt++].cost=t;
		}

		for(i=1;i<=W*H;i++){
			if(grave[i]==1 || hole[i]==1)
				continue;

			if((i+1)%W!=1 && (i+1)<=W*H && grave[i+1]==0){
				e[ecnt].from=i;
				e[ecnt].to=i+1;
				e[ecnt++].cost=1;
				if((i+1)!=W*H){
					e[ecnt].from=i+1;
					e[ecnt].to=i;
					e[ecnt++].cost=1;
				}
			}
			if((i-1)%W!=0 && (i-1)>0 && grave[i-1]==0){
				if(i!=W*H){
					e[ecnt].from=i;
					e[ecnt].to=i-1;
					e[ecnt++].cost=1;
				}
				e[ecnt].from=i-1;
				e[ecnt].to=i;
				e[ecnt++].cost=1;
			}
			if((i+W)<=W*H && grave[i+W]==0){
				e[ecnt].from=i;
				e[ecnt].to=i+W;
				e[ecnt++].cost=1;
				if((i+W)!=W*H){
					e[ecnt].from=i+W;
					e[ecnt].to=i;
					e[ecnt++].cost=1;
				}
			}
			if((i-W)>0 && grave[i-W]==0){
				if(i!=W*H){
					e[ecnt].from=i;
					e[ecnt].to=i-W;
					e[ecnt++].cost=1;
				}
				e[ecnt].from=i-W;
				e[ecnt].to=i;
				e[ecnt++].cost=1;
			}
		}
		sort(e,e+ecnt);

		negative_cycle=0;
		dist[1]=0;

		for(i=1;i<=W*H;i++){
			for(j=0;j<ecnt;j++){
				out=e[j];

				if(dist[out.from]!=INF && dist[out.to]>dist[out.from]+out.cost){
					dist[out.to]=dist[out.from]+out.cost;

					if(i==W*H)
						negative_cycle=1;
				}
			}
		}

		if(negative_cycle==1)
			printf("Never\n");
		else if(dist[W*H]==INF)
			printf("Impossible\n");
		else
			printf("%d\n",dist[W*H]);
	}

	return 0;
}

keith 6년 전 1

w와 h가 별로 크지 않아서, 저는 그냥 우선순위우선 탐색으로 (Queue대신 Priority Queue 사용) 시간을 가중치로 풀었는데, 동일하게 50%에서 오류가 납니다.

그래서 생각해 보니.. 문제 자체에 좀 함정이 있는듯 합니다. 설마 싶은데.. 혹시 제가 생각하는게 맞다면, 문제 자체에 명확히 해야 하는 부분이 있습니다.

확인해 본 후, 제가 생각한게 맞다면, 다시 댓글 달겠습니다.

keith 6년 전 2

50% 넘은 후에 시간초과가 뜨는걸 보니, 이유는 알아낸 것 같습니다. 문제 자체에 명확히 할필요는 굳이 없을것 같습니다만.
정말 깊게 생각하지 않는다면 당할것 같습니다..

이거 테스트 해보시지요... 이것에 많은 분들이 눈물을 흘리신듯. ㅜㅜ

qkdtmdeh 6년 전 1

이 문제를 풀어보지는 않아서.. (지금 이제부터 풀어볼 예정) 이게 문제일지는 모르겠지만 음의 사이클이 존재한다고 해서 무조건 never은 아닐것 같은데,,

음의 사이클이 존재하지만 그 사이클로부터 목적지에 도달할 방법이 없으면 음... never가 아니지 않을까요?

음의 사이클을 타지만 도착할 수 없을 경우에 대한 설명이 좀 애매한 것 같은데... 원문에서는 "For each test case, if it is possible for Scared John to travel back in time indefinitely, output Never. Otherwise, print the minimum time in seconds that it takes him to cross the graveyard from the entrance to the exit if it is reachable, and Impossible if not."라고 합니다. 즉 음의 사이클에 빠질 수 있는지가 그 사이클에서 도착점으로 갈 수 있는지보다 우선시되는 것 같습니다.

qkdtmdeh 6년 전 0

아그런가요? ㅎㅎ 부끄럽네요 ㅋㅋ

keith 6년 전 0

저도 @jh05013 님의 생각에 동의합니다.

굳이 음의 싸이클이 꼭 아니어도, 0의 싸이클이 존재해도 never가 되어야 하는걸로 보입니다. 제가 위에 올려놓은 예시가 그렇습니다.

원문을 자세히 보시면, "travel back in time indefinitely" 라는 말이 있는데, 계속해서 과거로 갔을때를 의미한다기 보다는 시간이 더이상 늘지 않고무제한으로 travel back 하는 경우가 있다면, Never가 떠야 할것 같습니다.

명확히 했으면 하는 부분은, 만약 무제한으로 돌아갈 수 있는 구간이 있으나, 그 구간으로 가는 길이 목적지보다 멀리 돌아가는 경우라고 한다면, Never인건지, 답을 출력해야 하는건지 확실치 않습니다.

keith 6년 전 0

명확히 해야 할 필요가 있는 예시 남겨봅니다.

시작점에서 종료까지 가장 짧은 길은 8이지만, 나가지 않고 돌아서 귀신구멍으로 가는 경우(길이 12), 무제한으로 반복할 수 있는 길이 있습니다.

이럴경우, 답이 Never인지, 8인지?

5
11
1
2
3
1
2
3
1
2
3
1
2
1
4 -11
0


보기 좋게 그려드리면,
0 0 0 F
1 1 0 0
1 1 1 0
1 1 1 0
S 1 1 1 2

S:시작점
F:종료점
못가는길(묘비)
귀신구멍(들어가는길)
귀신구멍(나오는길, 나왔을땐 시간은 -11)