[JAVA] 백준 1238: 파티

https://www.acmicpc.net/problem/1238

1238번: 파티

 

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

 

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

예제 입력 1 

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1 

10

 

---

1️⃣ 아이디어

N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생이 누구인지 구하는 문제이다.

이 문장만 보면 최대 거리를 구하는 문제인 것 같지만 조건을 다시 살펴보자.

 

학생들은 게을러서 최단 시간에 오고 가기를 원한다고 했다.

즉, 학생별로 파티 장소까지 오고 가는 최단 거리를 각각 구한 뒤, 여기서 최대값을 찾아주는 문제였다.

 

따라서 본 문제는 최단 거리를 구하는 알고리즘인 '다익스트라'를 활용하면 되겠다.

우선 문제를 풀기 위한 핵심 아이디어를 생각해보았다.

 

N명의 학생(마을)을 각각 노드로 보고, 파티 장소가 X 노드라고 생각하면 된다.

이 때 파티에 갔다가 다시 집으로 돌아와야 하기 때문에 두 부분으로 나눠 생각했다.

 

1) 1, 2, ... , N 번째 노드에서 X 번째 노드로 갈 수 있는 최단 경로

2) X 번째 노드에서 1, 2, ... , N 번째 노드로 갈 수 있는 최단 경로

 

즉, 일반 다익스트라 문제와 다르게 거리 배열을 2개로 만들어 각 마을에서 파티 장소까지의 최단 경로, 파티에서 각 마을까지의 최단경로의 합 중 최대 값이 문제의 정답이 되는 것이다.

---

2️⃣ 첫 번째 풀이 : 플로이드 + 다익스트라

 

가장 처음 생각했던 방법은 플로이드와 다익스트라를 함께 사용하는 방법이었다.

플로이드는 각 노드별 최단 거리를, 다익스트라는 한 노드에서 모든 노드까지의 최단거리를 구하는 알고리즘이다.

 

1) 플로이드

1. 2차원 배열에서 각 행의 X 번째 열은 각 노드별로 X까지의 최단거리이다.
2. 1차원 배열인 dist1 을 만들어 모든 행의 X 번째 열 값을 저장한다.
3. dist1 에 X 노드 (파티 장소) 까지의 최단 거리가 저장된다.

2) 다익스트라

1. 1차원 배열인 dist2 을 만들어 다익스트라를 수행한다.
2. dist2 에 X 노드로부터 모든 노드까지의 최단 거리가 저장된다.

 

예제 1의 경우 위 과정을 거치면 dist1, dist2 배열은 다음과 같을 것이다.

 

[ dist1 ]

노드	1	2	3	4
거리	1	0	3	7

 

[ dist 2]

노드	1	2	3	4
거리	4	0	6	3

 

예제 1에서 파티 장소는 2번 노드이기 때문에 다음과 같이 해석할 수 있다.

우선 dist1 을 보자. 

1->2 까지 최단 거리:1 , 3->2 까지 최단 거리:3 , 4->2 까지 최단 거리:7

 

dist2 을 보자.

2->1 까지 최단 거리:4 , 2->3 까지 최단 거리:6 , 2->4까지 최단 거리:3

이후 dist1 과 dist2 의 값을 합하여 가장 큰 값을 도출하면 답이 된다.

즉, 4번 노드의 값 (7+3 = 10) 이 가장 크기 때문에 정답은 10이 되는 것이다.

 

코드는 다음과 같다.

 

import java.util.*;
import java.io.*;

public class Main{
    static class Node implements Comparable<Node>{
        int v,cost;
        Node(int v,int cost){
            this.v=v;
            this.cost=cost;
        }
		
        @Override
        public int compareTo(Node o) {
            return this.cost-o.cost;
        }
    }
	
    static int N,M,X;
    static int INF=1000000000;
	
    static List<Node>graph[];
    static boolean visited[];
	
    static int xToN[];
    static int nToX[][];
	
    private static void Floyd() {
        for(int k=1;k<=N;k++) {
            for(int i=1;i<=N;i++) {
                for(int j=1;j<=N;j++) {
                    if(nToX[i][j] > nToX[i][k]+nToX[k][j])
                        nToX[i][j]=nToX[i][k]+nToX[k][j];
                }
            }
        }
    }
	
    private static void Dijkstra(int x) {
    	PriorityQueue<Node>q=new PriorityQueue<>();
    	xToN[x]=0;
    	q.offer(new Node(x,0));
		
    	while(!q.isEmpty()) {
    	    Node now=q.poll();
    	    if(visited[now.v]) continue;
    	    visited[now.v]=true;
			
    	    for(int i=0;i<graph[now.v].size();i++) {
                Node tmp=graph[now.v].get(i);
                int next=tmp.v;
                int value=tmp.cost;
                if(xToN[next] > xToN[now.v]+value) {
                    xToN[next]=xToN[now.v]+value;
                    q.offer(new Node(tmp.v,xToN[next]));
                }
    	    }
        }
    }
	
    public static void main(String[] args)throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer stk=new StringTokenizer(bf.readLine());
        
        N=Integer.parseInt(stk.nextToken());
        M=Integer.parseInt(stk.nextToken());
        X=Integer.parseInt(stk.nextToken());
        
        graph=new ArrayList[N+1];
        visited=new boolean[N+1];
        xToN=new int[N+1];
        nToX=new int[N+1][N+1];
        
        for(int i=1;i<=N;i++) 
        	graph[i]=new ArrayList<>();
        
        Arrays.fill(xToN, INF);
        for(int i=1;i<=N;i++) {
        	for(int j=1;j<=N;j++) {
        		if(i==j) nToX[i][j]=0;
        		else nToX[i][j]=INF;
        	}
        }
        
        for(int i=0;i<M;i++) {
        	stk=new StringTokenizer(bf.readLine());
        	int s=Integer.parseInt(stk.nextToken());
        	int e=Integer.parseInt(stk.nextToken());
        	int c=Integer.parseInt(stk.nextToken());
        	
        	graph[s].add(new Node(e,c));
        	if(nToX[s][e]>c) nToX[s][e]=c;
        }
        
        Floyd();
        Dijkstra(X);
        
        int xDist[]=new int[N+1];
        for(int i=1;i<=N;i++) {
        	xDist[i]=nToX[i][2];
        }
        
        int result=Integer.MIN_VALUE;
        for(int i=1;i<=N;i++) 
        	result=Math.max(xDist[i]+xToN[i], result);
        
        System.out.print(result);
    }
}

 

 

그런데 바로 시간 초과가 떴다.

그 이유를 찾아보니 플로이드 수행시 시간 복잡도를 생각하지 못한 것이다.

 

플로이드는 3중 for 문을 사용하기 때문에 O(n^3) 의 시간 복잡도를 가진다.

그런데 노드의 수는 1000개 이하기 때문에 1000^3 은 제한 시간인 1초를 넘길 수 있다.

따라서 해당 문제에 플로이드는 사용하면 안된다는 것을 알았다.

---

3️⃣ 두 번째 풀이 : 다익스트라

그렇다면 플로이드를 사용하지 않고 어떻게 모든 노드에서 X 노드까지의 최단 경로를 구할 수 있을까?

답은 생각보다 간단했다. 바로 간선의 방향을 거꾸로 생각하는 것이다.

 

만약 A 노드로부터 B 노드까지의 최단 경로가 존재한다고 하자. 방향이 있는 그래프에서 A->B 가 된다.

이 말은 즉  B 노드로부터 A 노드까지의 최단경로와 같다. B->A 인 것이다.

 

따라서 그래프를 저장할 때 시작 노드와 도착 노드를 반대로 바꾸어 저장한다. 

이 그래프에 다익스트라를 적용시켜 다시 X 번째 노드를 시작 노드로 바꾸면 이는 X 노드 -> 1~N 노드까지의 최단 거리이지만, 간선의 방향을 바꾸어 저장했기 때문에 1~N 노드 -> X 노드까지의 최단 거리가 된다.

 

이 방법을 사용하면 2차원 배열 생성시 불필요한 메모리를 절약할 수 있고, 시간 복잡도도 줄일 수 있다.

 

for(int i=0;i<M;i++) {
    stk=new StringTokenizer(bf.readLine());
    int s=Integer.parseInt(stk.nextToken());
    int e=Integer.parseInt(stk.nextToken());
    int c=Integer.parseInt(stk.nextToken());
			
    graph1[s].add(new Node(e,c));
    graph2[e].add(new Node(s,c));
}

 

위 코드처럼 그래프 저장시 방향을 바꾸어 한 번 더 저장해준다.

최종 코드는 아래와 같다.

 

import java.util.*;
import java.io.*;

public class Main{
	static int N,M,X;
	static final int INF=33333333;
	
	static List<Node>graph1[];
	static List<Node>graph2[];
	
	// 정방향, 역방향
	static int dist1[];
	static int dist2[];

	static class Node implements Comparable<Node>{
		int v,cost;
		Node(int v,int cost){
			this.v=v;
			this.cost=cost;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.cost-o.cost;
		}
	}
	
	private static int[] Dijkstra(int x,List<Node>graph[]) {
		PriorityQueue<Node> pq=new PriorityQueue<Node>();
		boolean visited[]=new boolean[N+1];
		int dist[]=new int[N+1];
		
		Arrays.fill(dist,INF);
		
		pq.offer(new Node(x,0));
		dist[x]=0;
		
		while(!pq.isEmpty()) {
			Node now=pq.poll();
			int nv=now.v;
			int nc=now.cost;
			
			if(visited[nv]) continue;
			visited[x]=true;
			
			for(int i=0;i<graph[nv].size();i++) {
				Node tmp=graph[nv].get(i);
				int tv=tmp.v;
				int tc=tmp.cost;
				
				if(dist[tv] > dist[nv]+tc) {
					dist[tv] = dist[nv]+tc;
					pq.offer(new Node(tv,dist[tv]));
				}
			}
		}
		return dist;
	}
	
	public static void main(String[] args)throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk=new StringTokenizer(bf.readLine());
		
		N=Integer.parseInt(stk.nextToken());
		M=Integer.parseInt(stk.nextToken());
		X=Integer.parseInt(stk.nextToken());
		
		graph1=new ArrayList[N+1];
		graph2=new ArrayList[N+1];
		dist1=new int[N+1];
		dist2=new int[N+1];
		
		// 초기값 세팅
		for(int i=1;i<=N;i++) {
			graph1[i]=new ArrayList<>();
			graph2[i]=new ArrayList<>();
		}
		
		// 입력
		for(int i=0;i<M;i++) {
			stk=new StringTokenizer(bf.readLine());
			int s=Integer.parseInt(stk.nextToken());
			int e=Integer.parseInt(stk.nextToken());
			int c=Integer.parseInt(stk.nextToken());
			
			graph1[s].add(new Node(e,c));
			graph2[e].add(new Node(s,c));
		}
		
		dist1=Dijkstra(X,graph1);
		dist2=Dijkstra(X,graph2);
		
		int result=0;
		
		for(int i=1;i<=N;i++) 
			result=Math.max(result, dist1[i]+dist2[i]);
		
		System.out.print(result);
	}
}

 

---

4️⃣ 알게된 점

한 노드로부터 모든 노드까지의 최단 거리는 다익스트라,

모든 노드에서의 최단 거리는 플로이드로 구할 수 있다.

 

이 문제를 통해 알게 된 사실은 방향 그래프가 주어졌을 때 플로이드를 사용하지 않고도 특정 노드까지의 최단 거리를 구할 수 있다는 것이다.

 

요즘 알고리즘 문제를 푸는게 너무 재미있다. 시험 기간인데 백준을 더 많이 하는 것 같다.

곧 종강인데 그동안 밀렸던 포스팅, 개발 공부 왕창 하고싶다.