ckdgus2482   7달 전

일단 아래 소스코드에서는 최단경로를 구하는 부분은 생략했습니다. 이 부분은 다른 문제에서 패스가 됐던 것으로 버그는 없을겁니다.

제가 시도한 풀이는 도로 방향을 반대로 뒤집은 네트워크와 그렇지 않은 네트워크 두개를 만들어서 각 네트워크에 대해서 파티가 열리는 마을로부터 나머지 각각의 마을까지 가는 최단경로의 길이를 구하고 이를 더한 값들 중 가장 큰 값을 출력하도록 하는 것이었습니다. 

그런데 답이 틀렸다고 나옵니다. 아무리 들여다 봐도 왜 틀린건지 납득이 안갔습니다. 그런데 이런저런 시도를 하던 중 발견한게 하나 있습니다.

제가 구현한 최단경로 알고리즘에서는 도달 불가능할때는 987654321을 반환하도록 되어있습니다. 혹시나 해서 16라인(게시한 소스코드 중)을 추가해봤는데 출력초과가 나옵니다. 즉, 테스트 케이스 중에 파티가 열린 마을로 왕복이 불가능한 학생(원문으로는 cow)가 있다는 겁니다. 그런데 문제에서는 이런 경우 어떻게 처리해야 할지 명시가 안되어있네요. 테스트 케이스를 수정하던지 문제에 이런 케이스에는 어떻게 처리해야할지를 명시해줘야할것 같습니다.


yukariko   7달 전

제 정답을 받은 코드에서는 왕복 불가능한 케이스가 있을 경우 반드시 틀리게 되어있는데

그게 아닌걸로 봐서 그런 케이스는 없는것 같네요.

제 생각에는 솔루션의 문제거나 이 코드 외의 다른 코드의 문제인것 같습니다.

joonas   7달 전

구현하신 함수의 구체적인 부분을 알려주셔야 할 것 같습니다.

ckdgus2482   7달 전

답변 감사합니다.

나머지 부분은 코드가 가독성이 좀 안좋아서 급한대로 주석을 달아봤습니다.

https://www.acmicpc.net/problem/1753 1753번 최단경로 문제에서 통과됐던 소스를 재사용한 것이구요.

tendList와 proxNode가 사실상 동일한 데이터인데 중복으로 저장한 이유는 64라인에서 노드 번호를 key로하여 search하는 부분과, 54라인에서 코스트가 가장 적은 경로를 찾는 부분 때문입니다. 이부분은 구현이 조잡하다고 생각은 드는데 마땅한 해결책이 떠오르지 않아서 일단 이렇게 했습니다.


joonas   7달 전

방향이 반대인 nw2.addLink(v, u, w); 는 있으면 안될거같은데요.

이 도로들은 단방향이기 때문에 라고 적혀있어요.

ckdgus2482   7달 전

그건 일부러 그렇게 한겁니다.

nw1은 X마을에서 각 마을로 돌아갈때의 길이를 구하기 위해 만든 네트워크이고, nw2는 모든 도로의 방향을 반대로 바꿈으로써 각 마을에서 X마을로 가는 경로를 X마을에서 각 마을로 가는 경로로 대신하도록 만든거에요.

yukariko   7달 전

음 코드가 길어서 전부 읽어보진 못했으나 예외 케이스는 찾았습니다.

3 3 2

1 2 2
2 3 1
3 1 5

이 경우  1 -> 2 로 가서 2 -> 3 - > 1 로 도착하면 8만에 갈 수 있는데,

위 코드에선 INF 보다 큰값이 나오게됩니다.

ckdgus2482   7달 전

감사합니다. 덕분에 해결했습니다.

탈출 조건 검사하는 순서가 조금 잘못 되어있었습니다.

이웃 노드 모두 검사하고 tendList 갱신 후에  tendList가 비었는지 확인해서 빠져나오니까 되네요.

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