[BOJ] 백준 1238번: 파티 (JAVA)

 

 

- 문제 출처 : https://www.acmicpc.net/problem/1238

 

---

1. 생각

저번 문제에 이어 이번에도 다익스트라 문제를 풀게 되었다.

 

기본 다익스트라와 다른 점은, 왕복으로 목적지를 갔다가 돌아오는 최소시간을 구하는 것인데,

간선들이 양방향이 아니라 단방향이라는 점에서 단순하게 걸린시간을 2배로 하는 게 아닌 점에서 고민이 필요했다.

 

2. 난관 & 해결방법

왕복을 처리하는 방법을 고민했을 때, 우선 dijkstra() 함수를 도착지인 X를 기점으로 1번 돌려서 

모든 마을에 대해서 N에서 출발해서 도착하는 최소시간을 구해두고,

각 마을에서 N으로 가는 최소시간을 dijkstra()를 각각 돌려 하나씩 구한 뒤, 두 결과를 더하면 되겠다고 생각했다.

 

static int dijkstra(int start, int end) {
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    boolean[] visited = new boolean[N + 1];
    int[] minTime = new int[N + 1];

    for (int i = 1; i <= N; ++i)
    {
        minTime[i] = INF;
    }

    minTime[start] = 0;
    pq.add(new Edge(start, minTime[start]));

    while (!pq.isEmpty())
    {
        Edge data = pq.poll();
        int to = data.to;
        int total = data.weight;

        if (visited[to])
            continue;

        if (to == end)
        {
            return total;
        }

        visited[to] = true;

        for (Edge e : edgeList.get(to))
        {
            int nowTo = e.to;
            int nowWeight = e.weight;

            if (!visited[nowTo] && minTime[nowTo] > nowWeight + total)
            {
                minTime[nowTo] = nowWeight + total;
                pq.add(new Edge(nowTo, minTime[nowTo]));
            }
        }
    }

    for (int i = 1; i <= N; ++i)
    {
        result[i] = minTime[i];
    }
    return 0;
}

 

다익스트라는 매개변수로 start와 end를 가지게 하여, 시작과 종료 지점을 지정할 수 있도록 했다.

 

그리고, 도착지인 X를 출발지로 잡고 그 값들을 저장할 때는 매개변수 end 값을 0으로 주어,
while문을 벗어난 뒤 for문에서 result 배열에 하나씩 값을 담도록 만들어뒀다.

 

이러면 우선 '도착지에서 출발지로 돌아가는 최소시간' 들이 모두 result에 담겨있는 상태가 된다.

 

dijkstra(X, 0);
for (int i = 1; i <= N; ++i)
{
    if (i == X)
        continue;
    result[i] += dijkstra(i, X);
}

int max = -1;
for (int i = 1; i <= N; ++i)
{
    if (i == X)
        continue;
    if (max < result[i])
        max = result[i];
}
System.out.println(max);

 

위의 코드는 main문에서 마지막 부분이다.

dijkstra(X, 0)을 통해 '도착지에서 출발지로 돌아가는 최소시간' 들을 다 담아뒀고,

 

그 다음 for문에서는 '각 마을에서 도착지로 가는 최소시간' 들을 담기 위해 dijkstra(i, X) 를 result[i]에 추가해줬다.

 

이렇게하면, 왕복으로 도착지를 다녀오는 최소시간들이 result에 모두 담겨있고,

여기서 최대값을 찾으면 문제에서 원하는 값을 찾을 수 있다.

 

3. 코드 및 결론

[ 전체 코드 ]

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

public class Main {
	
	static int N;
	static int M;
	static int X;
	static final int INF = 987654321;
	
	static int[] result;
	static List <List <Edge>> edgeList;
	
	static class Edge implements Comparable<Edge>{
		int to;
		int weight;
		
		public Edge(int to, int weight) {
			super();
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	static int dijkstra(int start, int end) {
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[N + 1];
		int[] minTime = new int[N + 1];
		
		for (int i = 1; i <= N; ++i)
		{
			minTime[i] = INF;
		}
		
		minTime[start] = 0;
		pq.add(new Edge(start, minTime[start]));
		
		while (!pq.isEmpty())
		{
			Edge data = pq.poll();
			int to = data.to;
			int total = data.weight;
			
			if (visited[to])
				continue;
			
			if (to == end)
			{
				return total;
			}
			
			visited[to] = true;
			
			for (Edge e : edgeList.get(to))
			{
				int nowTo = e.to;
				int nowWeight = e.weight;
				
				if (!visited[nowTo] && minTime[nowTo] > nowWeight + total)
				{
					minTime[nowTo] = nowWeight + total;
					pq.add(new Edge(nowTo, minTime[nowTo]));
				}
			}
		}

		for (int i = 1; i <= N; ++i)
		{
			result[i] = minTime[i];
		}
		return 0;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		
		result = new int[N + 1];
		edgeList = new ArrayList<>();
		for (int i = 0; i <= N; ++i){
			edgeList.add(new ArrayList<>());
		}
		
		for (int m = 0; m < M; ++m)
		{
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			edgeList.get(a).add(new Edge(b, c));
		}
		
		dijkstra(X, 0);
		for (int i = 1; i <= N; ++i)
		{
			if (i == X)
				continue;
			result[i] += dijkstra(i, X);
		}
		
		int max = -1;
		for (int i = 1; i <= N; ++i)
		{
			if (i == X)
				continue;
			if (max < result[i])
				max = result[i];
		}
		System.out.println(max);
	}
}

 

[ 결론 ]

 

상대적으로 생각하기는 쉬웠던 문제였지만, 최적의 방법은 아니었다.

N이 커지면 dijkstra를 모든 지점에 대해서 돌리는 것이 적합하지 않을 수 있기 때문이다.

 

따라서 AI와 함께 이를 분석해본 결과,

입력받은 도로의 방향만 뒤집은 새 그래프를 만들고 그에 대해서 dijkstra를 돌리면 되는 문제였다!

 

for (int i = 0; i <= N; ++i){
    edgeList.add(new ArrayList<>());
    edgeListReverse.add(new ArrayList<>());
}

for (int m = 0; m < M; ++m)
{
    st = new StringTokenizer(br.readLine());

    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());

    edgeList.get(a).add(new Edge(b, c));
    edgeListReverse.get(b).add(new Edge(a, c));
}

dijkstra(X, edgeList);
dijkstra(X, edgeListReverse);

 

이렇게 a, b를 뒤집어서 저장한 edgeListReverse를 만들고 이를 매개변수로 받도록 dijkstra를 수정하면

더욱 단순하게 코드를 구성할 수 있게 된다!

 

 

또한 메모리와 시간도 3배 이상 효율적으로 사용하는 최적의 방법이다.

이처럼 문제가 굉장히 쉽게 잘 풀려도 다른 사람의 코드나, AI가 만들어준 코드를 한번쯤 찾아보는 게 좋을 듯하다.