[backjoon]최단 경로/ 특정한 최단경로(1753/1504)

다익스트라 알고리즘을 공부하며 풀었던 문제!

왜 힘들어했는지 모르지만 공부 후 스스로 구현해 보며 상당히 어려워했었다.

1.  PriorityQueue에 <간선, 가중치>형식의 자료형을 넣어야 하는지를 제대로 이해하지 못했다. -> 속도를 위해 PriorityQueue를 써야하고 가중치를 기준으로 정렬되어야 한다.

2. 최단 경로를 저장하는 부분에서 프로세스에 대한 이해가 미흡.(뭔가에 씌였던 것인지 이해 불가임)

		while(!pQueue.isEmpty()) {
			Node cur = pQueue.poll();
			visit[cur.v] = true;
			for (int i = 0; i < arrList[cur.v].size(); i++) {
				Node next = arrList[cur.v].get(i);
				//nextWeight : 원래 next의 거리
				int nextWeight = distance[next.v];
				//updateNextWeight : 현재의 거리 + 현재 간선이 가지고 있는 가중치의 합
                int updateNextWeight = cur.weight + next.weight;
				//int updateNextWeight = distance[cur.vertax] + next.weight;
                //현재의 거리보다 새로 업데이트될 거리가 더 작다면 업데이트할 거리가 새로운 최단 거리가 된다.
				if(nextWeight > updateNextWeight) {
					distance[next.v] = updateNextWeight;
					pQueue.add(new Node(next.v, updateNextWeight));
				}
			}
		}

3. Integer.MAX_VALUE의 overflow : 쉽게 최대값을 잡지 말자 ㅜㅜ 예상치 못한 복경이었음.

4. 반드시 거쳐야하는 곳이 있다면 그 곳을 목적지로 하여 지나게 하면 됨!

ex) 1,2,3,4,5의 도시가 있는데 1에서 출발하여 5를 거쳐 2로 가야한다.

trip(source, destination) -> trip(1, 5); trip(5, 2);

5. 거리 탐색하려고 시작점을 기준으로 다 탐색하는데 시간 초과나 별 문제 없어서 내 이해의 부족함을 또 느꼈다.(아직도 분명하게 이해가 안 되지만 어쩔 수 없는 건가도 싶은?)

6. 어쩌다가 위상정렬을 먼저 공부했더니 다익스트라가 쉽게 느껴졌던...

 

여전히 알 수 없는 알고리즘이다.