[BOJ_1753 | Dikjstra]최단경로

풀이 문제 자체는 다익스트라 알고리즘을 이용해서 한 노드에서 다른 모든 노드들에 이르는최단 경로를 출력하면 되는 간단한 문제였다. 우선순위 큐 (Priority Queue)를 이용해서 다익스트라 알고리즘을 구현했고, 우선순위 큐를 이용하기 위해서 목적지 노드의 인덱스와 시작점으로부터의 거리를 저장하는 Element라는 원소 클래스를 정의하였다. *우선순위큐를 이용한 다익스트라 알고리즘은 시간 복잡도가 O(ElogV)정도이다. 문제는 간단했으나, 문제에 걸린 제약조건이 보기보다 꽤나 까다로웠다. 맨 처음에는 인접행렬과 Scanner를 통해 알고리즘을 수행했으나메모리초과와 시간초과가 동시에 발생하였다. 메모리 초과 이유는 인접행렬을 사용했기 때문인데,예를 들어 2만개의 노드가 존재한다면, Integer형을 ..

2019.01.24