6개월이 지나 이미 푸셨을지도 모르지만...
66-70줄의 문제점은 방문한 도시의 수를 구하고 있다는 점입니다. 답은 도로의 수입니다. 한 도시에 하나의 도로만 연결되어 있지는 않으니 오답이 나오게 됩니다.
답을 구하는 알고리즘을 다시 생각해보시고, 그 때에 '결과 구하신 이후에 경로 역추적 하실 때는 한 번 추적이 된 경우는 다시는 추적하지 않도록 해야 합니다.'의 의미를 다시 생각해보세요.
1948번 - 임계경로
6개월이 지나 이미 푸셨을지도 모르지만...
66-70줄의 문제점은 방문한 도시의 수를 구하고 있다는 점입니다. 답은 도로의 수입니다. 한 도시에 하나의 도로만 연결되어 있지는 않으니 오답이 나오게 됩니다.
답을 구하는 알고리즘을 다시 생각해보시고, 그 때에 '결과 구하신 이후에 경로 역추적 하실 때는 한 번 추적이 된 경우는 다시는 추적하지 않도록 해야 합니다.'의 의미를 다시 생각해보세요.
댓글을 작성하려면 로그인해야 합니다.
jeongbeen 3년 전
간선을 순방향으로 저장하고 역방향으로도 저장해줍니다.
순방향 간선을 탐색하여 maxdist를 구하고,
도착점에서 bfs로 역방향간선을 따라 maxdist일 때만 탐색하도록 시작점까지 돌려줍니다.
그리고 이 때 방문하는 정점들이 곧 maxdist일 때 거치게되는 도시라고 판단했습니다.
이러니까 틀렸습니다가 나와서
https://www.acmicpc.net/board/view/20705
글을 참고하여 해결했는데요.
위의 글에서
'결과 구하신 이후에 경로 역추적 하실 때는 한 번 추적이 된 경우는 다시는 추적하지 않도록 해야 합니다.'라고 하셨는데,
방문한 정점을 for문으로 직접 세어준다면, 다시 추적할 일도 없을텐데 왜 이렇게 풀면 안되는지 잘 모르겠습니다.
아예 판단 자체가 틀린거같은데, 틀린 이유를 못찾겠습니다... 반례 부탁드립니다.
감사합니다. ㅜㅜ