tddhot2   6년 전

- 소수 거리에 해당하는 애들만 인접행렬을 통해 그래프를 구현하였습니다.

- 그 그래프에서 DFS탐색와 DP를 이용해 최소값을 구했습니다.

- 다른 마을들 사이에서 A마을의 소수경로와 현재 소수마을에서의 다른마을로 못가는 경우등

다양한 테스트 케이스를 시도해봤습니다만.. 잘 풀리지 않네요

- 도움을 주시면 정말 감사하겠습니다.

wjdtmddnr24   6년 전

안녕하세요 :)

소스코드를 보니 dp 배열에 각 정점에서 출발하여 도착지점에 갈때의 최단 거리를 넣으시려고 하는것 같으신데 만약 visited배열에 이미 어떤 정점이 1이 체크되어있다면 그 정점으로 가는 경우를 확인하지 않는것 같습니다. 그렇게 되면 나중에 다시 visited배열에 0을 대입하신다고 해도 dp배열에 잘못된 값이 들어가있어 잘못된 값을 반환할 것입니다.

정리하자면 dp배열에 도착지점에 가는 최단거리가 대입되지 않을수 있기에 visited배열을 없애고 새로운 솔루션을 구상하시거나 다른 최단거리 알고리즘을 사용해 보시는게 좋을것 같아요 :)

cheetose   6년 전

너무 늦은 답변이라 보실 지는 모르겠는데 좌표값의 범위가 -3000~3000이라 거리의 최대값은 4200이 아니라 8500쯤 됩니다

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