jeongbeen   3년 전

간선을 순방향으로 저장하고 역방향으로도 저장해줍니다.

순방향 간선을 탐색하여 maxdist를 구하고,

도착점에서 bfs로 역방향간선을 따라 maxdist일 때만 탐색하도록 시작점까지 돌려줍니다.

그리고 이 때 방문하는 정점들이 곧 maxdist일 때 거치게되는 도시라고 판단했습니다.

이러니까 틀렸습니다가 나와서

https://www.acmicpc.net/board/view/20705

글을 참고하여 해결했는데요.


위의 글에서

'결과 구하신 이후에 경로 역추적 하실 때는 한 번 추적이 된 경우는 다시는 추적하지 않도록 해야 합니다.'라고 하셨는데,

방문한 정점을 for문으로 직접 세어준다면, 다시 추적할 일도 없을텐데 왜 이렇게 풀면 안되는지 잘 모르겠습니다.

아예 판단 자체가 틀린거같은데,  틀린 이유를 못찾겠습니다... 반례 부탁드립니다.

감사합니다. ㅜㅜ

playsworld16   3년 전

6개월이 지나 이미 푸셨을지도 모르지만...

66-70줄의 문제점은 방문한 도시의 수를 구하고 있다는 점입니다. 답은 도로의 수입니다. 한 도시에 하나의 도로만 연결되어 있지는 않으니 오답이 나오게 됩니다.

답을 구하는 알고리즘을 다시 생각해보시고, 그 때에 '결과 구하신 이후에 경로 역추적 하실 때는 한 번 추적이 된 경우는 다시는 추적하지 않도록 해야 합니다.'의 의미를 다시 생각해보세요.

jeongbeen   3년 전

결국 원인을 찾지 못하고 66-70줄을 지워서 풀었는데, 

이제라도 원인을 알게되어 속이 시원하네요 ㅎㅎ

감사합니다! 덕분에 해결됨 마크 답니다 ^^bb

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