k550706   1년 전

단순히 다익스트라로 처리해보니 바로 시간초과가 뜹니다

다른 로직이 있을거 같은데, 다른분들의 질답을 읽어봐도 잘 모르겠습니다ㅠ

영감이 좀 필요한데, 혹시 좀 알수 있을까요?

qhsl1213   1년 전

이 문제는 그냥 풀 경우 간선이 너무 많아서 시간초과가 발생합니다.

그러므로 사실상 쓸모없는 간선들을 모두 제거하여 시간초과를 방지해야 합니다


일단 이 문제에선 각 마을의 좌표를 3차원으로 표현하고 있는데, (x, y)의 2차원만 있다고 생각해봅시다.

마을의 수가 20만 개이면, 각 마을 당 다른 모든 마을로 이동할 수 있으므로 199999개의 간선이 있습니다.

마을이 20만개이므로, 200000*199999개의 간선이 있는 상태입니다.


그런데 여기엔 쓸모없는 간선이 너무 많습니다.

예를 들어 세 정점 (1, 3), (3, 8), (5, 20)이 있다고 해봅시다.

(1, 3) -> (3, 8)로 가는 가중치 2짜리 간선이 있고, (3, 8) -> (5, 20)으로 가는 가중치 2짜리 간선이 있습니다.

또한 (1, 3) -> (5, 20)으로 가는 가중치 4짜리 간선이 있습니다. 이 간선은 필요가 없습니다. 왜냐하면 (1, 3) -> (3, 8) -> (5, 20)으로 가는 것과 같기 때문입니다.


즉, 각 마을은 각 축을 기준으로 자신과 가장 가까이 있는 마을로만 갈 수 있는 간선만 있으면 됩니다(표현을 굉장히 뭉뚱그려서 표현한 것입니다. 실제로 어떻게 구현해야 할 지 생각해보시면 될 듯합니다).

z축에 대해선 아래의 대회 에디토리얼을 참고해주시면 될 것 같습니다.

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








k550706   1년 전

와우 친절한 설명 및 자료 정말 감사드립니다!

정독 후에 처리해보도록 하겠습니다!

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