문제 링크 : https://www.acmicpc.net/problem/1238
모든 마을에서 출발하여 X 마을에 들렀다가 다시 돌아오는 길이 가장 큰 값을 구하는 문제입니다.
N이 크지 않아서 플로이드와샬, 다익스트라 어느것으로 해도 풀리는 문제입니다.
하지만 X에 대한 최단 경로만 구하면 되는 상황에서 모든 정점에 대해 다익스트라를 하는 것은 비효율 적입니다.
그래서 'X마을 -> 다른 모든 마을' 의 최단경로와 '다른 모든 마을 -> X마을' 의 최단경로.
단 두번만 다익스트라를 돌려서 문제를 해결할 수 있습니다.
X마을에서의 최단 경로는 시작점을 X로 놓고 하면 되지만
X마을로 향하는 최단 경로는 조금 다릅니다.
입력받는 간선의 값을 전부 뒤집어서 넣은 뒤에 시작점을 X로 하여 구해야 합니다.
인접행렬을 예로 들면 원래는 edge[v1][v2] = cost 이렇게 입력하는 식을 edge[v2][v1] = cost 로 입력한 edge 배열을 이용하여 구할 수 있습니다.
저는 처음부터 인접리스트를 두개 생성하여 구하는 방법으로 하였습니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| import java.io.*; | |
| // https://www.acmicpc.net/problem/1238 | |
| class Main { | |
| static int stoi(String s) { return Integer.parseInt(s);} | |
| static final int INF = 987654321; | |
| static int N, M, X; | |
| static int[] dist, revDist; | |
| static List<List<Node>> list, revList; | |
| // 마을의 번호와 시작점으로부터의 거리를 저장하는 Node 클래스 | |
| // 거리가 짧은 순으로 자동으로 정렬되게 comparable 를 오버라이드 | |
| static class Node implements Comparable<Node> { | |
| int index; | |
| int distance; | |
| public Node(int index, int distance) { | |
| this.index = index; | |
| this.distance = distance; | |
| } | |
| public int compareTo(Node n) { | |
| return this.distance - n.distance; | |
| } | |
| } | |
| public static void main(String[] args) throws Exception { | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| StringTokenizer st; | |
| // input data | |
| st = new StringTokenizer(br.readLine()); | |
| N = stoi(st.nextToken()); | |
| M = stoi(st.nextToken()); | |
| X = stoi(st.nextToken()); | |
| dist = new int[N+1]; | |
| revDist = new int[N+1]; | |
| list = new ArrayList<List<Node>>(); | |
| revList = new ArrayList<List<Node>>(); | |
| // 각 거리 초기화 | |
| init(); | |
| for(int i=1; i<=M; i++) { | |
| st = new StringTokenizer(br.readLine()); | |
| int v1 = stoi(st.nextToken()); | |
| int v2 = stoi(st.nextToken()); | |
| int dist = stoi(st.nextToken()); | |
| list.get(v1).add(new Node(v2, dist)); | |
| revList.get(v2).add(new Node(v1, dist)); | |
| } | |
| // solve | |
| // 다익스트라 2번을 이용해서 구할 수 있다 | |
| // 주어진 간선에서 X번 마을에서 각 마을로 가는 최단 경로를 구하고 | |
| dijkstra(list, dist, X); | |
| // 간선을 뒤집은 다음에 X번 마을에서 각 마을로 가는 최단 경로를 구하면 | |
| // 각 마을에서 X번 마을로 가는 최단 경로를 구할 수 있음 | |
| dijkstra(revList, revDist, X); | |
| // answer | |
| int max = -1; | |
| for(int i=1; i<=N; i++) | |
| max = Math.max(max, dist[i] + revDist[i]); | |
| System.out.println(max); | |
| } | |
| static void init() { | |
| Arrays.fill(dist, INF); | |
| Arrays.fill(revDist, INF); | |
| for(int i=0; i<=N; i++) { | |
| list.add(new ArrayList<Node>()); | |
| revList.add(new ArrayList<Node>()); | |
| } | |
| } | |
| static void dijkstra(List<List<Node>> list, int[] distance, int start) { | |
| boolean[] visited = new boolean[N+1]; | |
| PriorityQueue<Node> pq = new PriorityQueue<Node>(); | |
| distance[start] = 0; | |
| pq.add(new Node(start, 0)); | |
| while(!pq.isEmpty()) { | |
| int idx = pq.poll().index; | |
| // 방문한 곳은 또 방문할 필요 없음 | |
| if(visited[idx]) continue; | |
| visited[idx] = true; | |
| for(Node node : list.get(idx)) { | |
| // node.index 까지의 거리는 (시작점->idx 거리 + idx->node.index 거리) 중 더 작은 것 | |
| if(distance[node.index] > distance[idx] + node.distance) { | |
| distance[node.index] = distance[idx] + node.distance; | |
| pq.add(new Node(node.index, distance[node.index])); | |
| } | |
| } | |
| } | |
| } | |
| } |
'알고리즘 문제 > 백준' 카테고리의 다른 글
| 백준 1620번. 나는야 포켓몬 마스터 이다솜 (Java) (0) | 2019.03.22 |
|---|---|
| 백준 1697번. 숨바꼭질 (Java) (0) | 2019.03.22 |
| 백준 1753번. 최단경로 (Java) (0) | 2019.03.02 |
| 백준 10815번. 숫자 카드 (Java) (0) | 2019.02.16 |
| 백준 2240번. 자두나무 (Java) (0) | 2019.02.15 |