juhongkim2   2년 전

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

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

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

W=4, H=3일때

S 0 0 H

0 0 G G 

0 0 0 E

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

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

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

 

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

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

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


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

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

keith   2년 전

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

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

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

keith   2년 전

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

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

qkdtmdeh   2년 전

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

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

jh05013   2년 전

음의 사이클을 타지만 도착할 수 없을 경우에 대한 설명이 좀 애매한 것 같은데... 원문에서는 "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   2년 전

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


keith   2년 전

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

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

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

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

keith   2년 전

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

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

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

jh05013   2년 전

정해 코드에 맨 위에 주어진 ("2 2 1 1 -2"가 있는) 입력을 넣었을 때 8이 나오는 것으로 보아 0의 사이클은 포함하지 않는 것 같습니다. 제가 언급하려고 한 것은 "음의 사이클에 빠진 다음에 도착으로 갈 수 있는지 검사해야 되는가"였습니다.

바로 위에 있는 입력도 8이 나옵니다.

keith   2년 전

@jh05013 님 만약 저기서, -11 이 아닌, -12 인경우는 Never인가요? 아니면 그래도 8인가요?

jh05013   2년 전

입력 형식이 잘못됐네요. "0 4 -11"를 "0 4 1 0 -11"로 바꿔야 합니다.

이렇게 수정해도 8이 나오고, -12로 바꾸면 Never가 나옵니다.


juhongkim2   2년 전

해결했습니다.

바꾼부분은 별거없고 저기 edge넣어주는 부분에서 if문 처리한 부분들 다 빼줬습니다.

그리고 한가지 도착지점인 E에서는 나가는 간선이 없어야 합니다.

이부분에 대한 반례는 잘 생각해보시면 될듯...

keith   2년 전

@jh05013 감사합니다.^^; 이제 명확해진거 같습니다. 이거 문제 자체가 정말 깊게 생각하지 않으면 함정이 많네요..^^; 

음의 사이클 부터 찾고 시작하면 정답이고, 일단 짧은 거리부터 탐색하게 되면, 오답이군요.. 일단은, 곰곰히 정말 자세히 따져보면, jh05013님이 풀이하시는 방법이 맞는것 같습니다.

위의 예에서(-12 일때), 3,4위치에 있을때, 그냥 나가버리는 것 보다, 돌아서 가는것이 더 빠른 경우가 생길 수 있게 되어버리고, 그러다 보면 음의 싸이클을 타게 되지만, 단순한 탐색으로는 3,4에 있으면 그냥 나가버리는게 그 순간 가장 짧은 길이 되어버리네요.

rkr638   1년 전

혹지 진심 생각이 안나서그러는데 도착지점에 왜 간선이 없어야 하는지 설명해주실수 있으신가요????

도착지에 간선이 있어도 최소가 안되지 않아요??

jh05013   1년 전

번역본에는 애매하게 주어져 있는데 원문에서는 명확합니다.

"he will leave as soon as he reaches it, determined never to set foot anywhere in the graveyard again."

rkr638   1년 전

헐 넘나빠르시네요 감사합니다^^

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