[백준 1238] 파티 (자바)

 

난이도 : 골드 3

 

다익스트라 알고리즘을 이용해 풀었습니다.

2020/11/02 - [문제풀이/자바] - [백준 1753] 최단경로 (자바)

[백준 1753] 최단경로 (자바)

위 링크에 다익스트라 설명이 있습니다.

 

1~N을 출발점으로 파티 마을 X까지의 거리를 다익스트라로 구했습니다.

그리고 반대로 파티 마을 X를 출발점으로 다익스트라를 돌려서 각 마을까지의 거리를 구했습니다.

그리고 이 두 값을 마을마다 더해주면 오고 가는 거리가 나오는데 이 값들 중 최댓값을 구하면 됩니다.

---

전역 변수

LinkedList<Node> list[] = 문제에서 주어진 간선

int distance[] = 가중치의 값

boolean visit[] = 방문 확인 배열

 

함수

void main

time 배열은 파티 마을까지 오고 가는 거리의 값입니다.

1~N마을을 출발지로 다익스트라를 돌린 후 X까지의 거리를 time에 더해줍니다.

그 후 X를 출발지로 각 마을까지 거리를 구하여 time에 더해줍니다.

time의 값들 중 최대값을 출력합니다.

(dijkstra 호출)

 

void dijkstra

우선순위 큐에 시작 정점을 넣어줍니다. 그리고 시작 지점의 가중치는 0입니다.

visit, distance를 초기화하고 distance에는 -1을 넣어줍니다.

우선순위 큐가 빌 때까지 while문을 반복합니다.

현재 정점에 방문하지 않았을 때 연결된 정점들에 대해 검사를 시작합니다.

연결된 정점의 가중치가 -1이거나 연결된 정점의 가중치가 현재 정점의 가중치와 현재 간선의 가중치의 합보다 클 때 값을 업데이트합니다.

업데이트 후 다음 정점을 우선순위 큐에 넣어줍니다.

 

class Node

노드는 정점의 번호와 가중치를 가집니다.

우선순위 큐의 타입으로 이용하기 위해 Comparable을 implements 해줍니다.

정렬 기준은 가중치의 오름차순입니다.