[백준 - Java] 1238번 : 파티

문제

www.acmicpc.net/problem/1238

1238번: 파티

설명

다익스트라 알고리즘을 이용해 구현하면 된다.

 

📌 더 자세히 알고 싶다면 아래 포스팅을 참고해주세요

 

[Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘

 

하지만 각 구현 방식에 따라 걸리는 시간과 메모리가 천차만별이다.

 

1. 인접 행렬로 정점과 간선을 표현하고, 기본 다익스트라 알고리즘을 이용해 구현 (2992, 2360 ms)

N개의 마을에서 X까지 N번, X에서 N개의 마을까지 N번

즉, N^2만큼 다익스트라 함수를 돌려 구현함. 생각이 짧았다..

성공은 하지만 시간이 굉장히 많이 걸림

 

(그래도 위와 같은 방식을 인접 리스트와 우선순위 큐를 이용한 다익스트라 방식으로 풀면 반 넘게 시간이 줄긴 함) (764ms)

 

2. 생각해보면 다익스트라 함수를 1번과 같이 많이 돌릴 이유가 없음. (시간 훨씬 단축) (220 ms)

왜냐하면 파티를 하는 지점인 X는 고정이기 때문이다.

딱 2번만 돌려 최단거리를 구하면 된다.

 

첫 번째, X마을을 시작으로 N개의 학생 집까지 가는 최단거리 구하기.

X를 시작점으로 다익스트라를 돌리면 N개의 마을까지의 최단거리가 distance 배열에 저장된다. 

 

두 번째, N개의 학생 집에서 X마을까지의 최단 거리 구하기.

이는 주어진 간선의 방향을 모두 뒤집은 인접 리스트에서 X를 시작점으로 다익스트라를 돌리면 된다.

( "x에서 y로 가는 경로"의 간선의 방향을 뒤집으면 "y에서 x로 가는 경로"가 되기 때문.)

이해가 어렵다면 아래 링크를 참고해주세요.

 

www.acmicpc.net/board/view/22523

전체 코드

2번 방식으로 구현한 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main3 {
	static int INF;
	static int N, X;
	static ArrayList<Element>[] adjList1, adjList2;
	static int[] distance1, distance2;
	static boolean[] check;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());		
		int M = Integer.parseInt(st.nextToken());		
		X = Integer.parseInt(st.nextToken());

		INF = 100 * (N-1);

		adjList1 = new ArrayList[N+1]; // 1 : X에서 각 마을까지의 최단 거리를 구하기 위한 인접 리스트 
		adjList2 = new ArrayList[N+1]; // 2 : 주어진 간선을 뒤집어 저장. 즉, 각 마을에서 X까지의 거리를 구하기 위한 인접 리스트 

		distance1 = new int[N+1];
		distance2 = new int[N+1];

		for(int i = 1; i < N+1; i++) {
			adjList1[i] = new ArrayList<>();
			adjList2[i] = new ArrayList<>();
		}

		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());	
			int end = Integer.parseInt(st.nextToken());	
			int t = Integer.parseInt(st.nextToken());	

			adjList1[start].add(new Element(end, t));
			adjList2[end].add(new Element(start, t));
		}

		dijkstra(X, adjList1, distance1); // X마을에서 N개의 학생 집까지의 최단 거리 구하기(X가 고정이기 때문에 가능) 
		dijkstra(X, adjList2, distance2); // N개의 학생 집에서 X마을까지의 최단 거리 구하기

		int time = 0;

		for(int n = 1; n <= N; n++) {
			time = Math.max(time, distance1[n] + distance2[n]);
		}

		System.out.println(time);
	}

	public static void dijkstra(int start, ArrayList<Element>[] adjList, int[] distance) {
		check = new boolean[N+1]; // 정점이 집합 S에 속하는지 아닌지를 판별할 배열 
		Arrays.fill(distance, INF); // 무한대로 초기화 

		distance[start] = 0;

		PriorityQueue<Element> pq = new PriorityQueue<>();
		pq.offer(new Element(start, 0));

		while(!pq.isEmpty()) {
			int current = pq.poll().index;

			if(check[current]) continue;
			check[current] = true;

			for(Element next : adjList[current]) {
				if(distance[next.index] > distance[current] + next.distance) {
					distance[next.index] = distance[current] + next.distance;
					pq.offer(new Element(next.index, distance[next.index]));
				}
			}
		}
	}

}

class Element implements Comparable<Element> {
	int index;
	int distance;

	Element(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}

	@Override
	public int compareTo(Element o) {
		return Integer.compare(this.distance, o.distance);
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%231238/src/Main3.java

KwonMinha/BOJ