[JAVA] 최소 거리를 찾아주는 다익스트라 알고리즘

조건 1. 음수인 거리가 있으면 안됨 (무조건 양수)

시간복잡도 : O(ElogV)

 

웬만하면 PQ + 다익스트라로 접근하면 좋을 거 같음

(그렇다고 우선순위 큐를 사용했을 때, 기본 다익스트라 알고리즘보다 절대적으로 속도가 빠른건 아님)

(근데 그게 어느경우인지 아직 잘 모르겠음 ㅜ)

 

(문제 자체도 비공개 문제이고 나만 알아보면 되니까 좀 코드가 친절하지 않음ㅎ_ㅎ)

(혹시 검색으로 들어오시는 분이 계시다면 죄송합니다 구냥 여긴 저의 메모장입니다 ㅜ)

 

그래도 간단히 써보자면 mStart라는 노드에서 다른 노드로 갈 때 최소시간이 얼마인지를 cost라는 배열에 정리한 것 임다.

 

PriorityQueue <node_info> pq = new PriorityQueue<>();
int [] visited = new int[n];
int [] cost = new int[n];
		
for(int i=0;i<n;i++) {
	cost[i] = inf;
}
		
cost[mStart] = 0;
// mStart --> mStart 까지 가는 건 거리가 0임 
node_info start_node = new node_info(mStart, 0);
pq.add(start_node);
		
while(pq.size() != 0) {
	node_info thisnode = pq.poll();
	if(visited[thisnode.startnode]==1) {
		continue;
	}
    
    if(thisnode.startnode == mEnd) {
		break;
	}
    
	visited[thisnode.startnode] = 1;
			
	for(int i=0;i<n;i++) {
		if(i==thisnode.startnode) {
			continue;
		}
				
		if(thisnode.calculation + money[thisnode.startnode][i] < cost[i]) {
			cost[i] = thisnode.calculation + money[thisnode.startnode][i];
			pq.add(new node_info(i, cost[i]));
		}
	}
}

 

느낀점 : PQ 진짜 엄청엄청 필수임. 근데 왜 코테공부할 땐 PQ공부 안했지;

PQ를 쓸 줄 알면 진짜진짜 편하고, 시간 절약을 정말 많이 할 수 있다.

다만, PQ의 특성을 제대로 이해하고 Break를 적절한 곳에 적합하게 잘 사용해줘야한다.

(방금도 Break 하나로 100ms 정도 시간단축 성공, 저번에는 Break 안걸어줬을 때는 시간초과, 걸어주니까 통과 한 경험도 존재)

 

나는 최소거리문제를 보통 PQ + BFS로 접근을 했는데, 다익스트라로 접근하는 것이 훨씬 시간을 적게 사용한다.

(적어도 이 문제에 대해서는 그랬다)

그래서, 다익스트라 공부해보았는데 이렇게 직접 구현하는 것도 연습하고 이제 다음 연습할 거는 레퍼런스 코드 활용하는 거 연습해야겠따.

올만에 글쓰니까 재밌어서 주절주절 그럼 뿅