백준 9694번 - 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

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

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

 

 

대표적인 다익스트라 알고리즘을 통해 구현해주는 문제이다.

 

다익스트라(Dijkstra) 알고리즘은 최단경로 탐색 알고리즘으로서

 

특정한 하나의 정점에서 다른 정점으로 가는 최단 경로를 알려준다. 

 

예를들어 0,1,2,3,4 의 사람이 있고 각자의 친밀도를 간선으로 표시하면 아래와 같다.

 

문제에서 0번째 사람이 마지막 번째 사람(4번-최고의원)을

 

만날때까지 친밀도의 합이 최소가 되어야 하고,

 

마지막 인원(4번-최고의원)을 만날 수 없을때에는 -1을 출력하라고 되어 있다.

 

물론 위와같이 0인 사람과 3인 사람의 친밀도가 4

 

3인사람과 4인 사람의 친밀도가 3 즉 4 + 3 = 7 의 친밀도를 통해서 최고의원을 만나는 방법도 있지만,

 

아래와 같은 방법으로 최고의원을 만나면 더 낮은 친밀도 점수를 얻어서 만날 수 있다.

 

0(1) -> 1(1) -> 2(3) -> 4

 

총 5의 친밀도 점수로 위의 친밀도 점수 7보다 낮은 수치가 된다.

 

즉, 다익스트라 알고리즘을 사용하여 최소비용을 가지는 경로를 구하면 되는 문제이다.

 

 

 

1.JAVA 를 통한 풀이

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

public class Main {
	
	static ArrayList<ArrayList<Node>> map;
	static int[] answer;
	static int[] prev;
	static int T,N,M;
	static int INF = Integer.MAX_VALUE;
	static int CASE = 1;
	
	static class Node {
		int o,w;
		
		public Node(int o, int w) {
			this.o = o;
			this.w = w;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			N = Integer.parseInt(stk.nextToken());//관계의 개수
			M = Integer.parseInt(stk.nextToken());//정치인의 수
			
			
			prev = new int[M];
			answer = new int[M];
			map = new ArrayList<ArrayList<Node>>();
			
			clean();
			
			for (int i = 0; i < M; i++) {
				map.add(new ArrayList<>());
			}
			
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int r = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int w = Integer.parseInt(st.nextToken());
				
				map.get(r).add(new Node(c,w));
				map.get(c).add(new Node(r,w));
			}
			
			dijkstra();
			
		}//while
	}//main()
	
	static void dijkstra() {
		
		PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
			@Override
			public int compare(Node n1, Node n2) {
				
				if (n1.w > n2.w) return -1;
				else if (n2.w > n1.w) return 1;
				else return 0;
			}
		});
		
		answer[0] = 0;
		pq.offer(new Node(0,0));
		
		while(!pq.isEmpty()) {
			Node nd = pq.poll();
			int cur = nd.o;
			int curW = -nd.w;
			
			if (answer[cur] < curW) continue;
			
			for (int i = 0; i < map.get(cur).size(); i++) {
				int next =  map.get(cur).get(i).o;
				int nextW =  map.get(cur).get(i).w;
				
				if (answer[next] > curW + nextW) {
					answer[next] = curW + nextW;
					pq.offer(new Node(next,-answer[next]));
					prev[next] = cur;
				}
			}
		}//while
		
		
		if (answer[M-1] == INF) System.out.printf("Case #%d: -1\n",CASE++);
		else {
			Stack<Integer> stack = new Stack<>();
			
			for (int i = (M-1); i > 0;) {
				stack.push(i = prev[i]);
			}

			System.out.printf("Case #%d:",CASE++);
			
			while(!stack.empty()) {
				System.out.printf(" %d",stack.pop());
			}
			
			System.out.printf(" %d\n",M-1);
		}
		
		
	}//dijsktra()
	
	static void clean() {
		for (int i = 0; i < M; i++) {
			answer[i] = INF;
			prev[i] = -1;
		}
	}
	

}

 

 

2. C++ 를 통한 풀이

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <climits>
#define MAX 21
using namespace std;

int INF = INT_MAX;
int CASE = 1;
int T,N,M;
vector < pair<int,int> > edge[MAX];
int prev_map[MAX];
int visit[MAX];

void clear() {
    for (int i = 0; i < MAX; i++) {
        visit[i] = INF;
        prev_map[i] = -1;
        edge[i].clear();
    }
}

void dijkstra() {
   priority_queue < pair<int,int> > pq;  
   visit[0] = 0;
   pq.push(make_pair(0,0));
   
   while(!pq.empty()) {
       int cur = pq.top().first;
       int cur_w = -pq.top().second;
       
       pq.pop();
       
       if (visit[cur] < cur_w) continue;
       
       for (int i = 0; i < edge[cur].size(); i++) {
           int next = edge[cur][i].first;
           int next_w = edge[cur][i].second;
           
           if (visit[next] > cur_w + next_w) {
               visit[next] = cur_w + next_w;
               pq.push(make_pair(next,-visit[next]));
               prev_map[next] = cur;
           }
       } 
   }//while
   
   if (visit[M-1] == INF) cout << "Case #" << CASE++ << ": -1\n";
   else {
       stack<int> stk;
       
       for (int i = (M-1); i > 0;) {
           stk.push(i = prev_map[i]);
       }
       
       cout << "Case #" << CASE++ << ":";
       
       while(!stk.empty()) {
          cout << " " << stk.top();
          stk.pop();
       }
       
       cout << " " << M-1 <<"\n";
   }
}

int main()
{   
    
    cin >> T;
    
    while(T--) {
        cin >> N >> M;
        clear();
        
        for (int i = 0; i < N; i++) {
            int r,c,w;
            cin >> r >> c >> w;
            
            edge[r].push_back(make_pair(c,w));
            edge[c].push_back(make_pair(r,w));
        }
        
        dijkstra();
    }//while

    return 0;
}