citizen   7년 전

간선에 대한 2차원 배열을 설정하면 메모리가 초과되서

정점에 관한 클래스를 선언하고 간선으로 이어지는 정점 번호에 대한 리스트와 각 정점까지 거리에 대한 리스트를 지정해주었습니다.

정점(Point)의 생성자를 호출할 때 최단거리를 INF로 초기화시켜주었구요.

주어지는 E개의 줄에 대해 정점의 정보를 추가해주었습니다.(next의 i번쨰 인덱스값은 i번째로 연결된 또 다른 정점의 번호이며,

dis의 i번째 인덱스값은 그 정점까지의 거리입니다.)

그리고 무난하게 우선순위큐를 만들어서 매 과정마다 최단거리인 정점을 방문하도록 하였는데요.

이 때, Comparator를 각각의 번호(Integer)에 해당하는 정점의 최단거리를 기준으로 오름차순으로 작동하도록 구현하였습니다.

while문 내부는 이미 방문한 정점인지 아닌지 체크를 꾸준히 하면서 연결된 정점의 최단거리를 갱신합니다.


4%정도 진행하다가 틀렸습니다가 나와버리는데 반례라도 제시해 주셨으면 합니다.  

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