[백준] 18223 민준이와 마산 그리고 건우 - JAVA

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

 

18223번: 민준이와 마산 그리고 건우

 

❔플로이드 와샬법으로 풀까 했지만 입력값이 크고, 출발지와 도착지가 정해져 있기 때문에 패스 

 

 

알고리즘

• 출발지→도착지 최단 경로 , 출발지→건우 최단경로, 건우 → 도착지 최단경로를 알아야 한다. 
• 출발지→도착지 == (출발지→건우) + (건우→도착지) 라면, 건우를 데리고 마산에 갈 수 있다. 
• 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하기 위한 다익스트라 알고리즘을 활용하여 접근한다. 
• 음의 가중치를 포함하고 있지 않기 때문에 가능 ! 

---

 

구현 과정

• Node 클래스 : 각 노드의 정보를 담고 있는 클래스 (노드 번호, 출발지로부터 해당 노드까지의 최단거리) 
• map[][] : 각 노드간 연결되어 있는 간선 정보를 담고 있는 2차원 정수 배열 
• dis[] : 출발 정점으로부터 다른 모든 정점까지의 최단 거리 저장하는 배열 
• check[] : 해당 정점을 거쳐가는 경로를 탐색했는지 확인하기 위한 boolean형 배열 

 

1. 그래프의 간선 정보를 map[][] 배열에 저장한다. (ex) 1 - 2 노드간 거리가 1이라면 map[1][2] = map[2][1] =1) 

 

2. 다익스트라 알고리즘을 사용하여 출발지(민준)→도착지 / 출발지(민준)→건우 / 건우→도착지 각 경로의 최단 거리값을 구한다. 

 

3. 출발지→도착지의 값이 출발지→건우→도착지의 값과 같다면, 민준이는 건우를 도울 수 있다. 즉, 출발지→도착지 == (출발지→건우) + (건우→도착지) 일 경우 "SAVE HIM", 그렇지 않다면 "GOOD BYE"

 

💡다익스트라 참고

[Algorithm] 다익스트라(Dijkstra) 알고리즘

---

 

소스 코드 

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

public class Solution_BaekJoon_18223 {
	static class Node implements Comparable<Node>{
		int node_num;
		int weight; 
		
		public Node(int node_num, int weight) {
			this.node_num = node_num;
			this.weight = weight; 
		}

		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight; 
		}
		
	}
	
	static int map[][]; 
	static int v ;
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st= new StringTokenizer(br.readLine(), " "); 
		v= Integer.parseInt(st.nextToken()); //정점의 갯수
		int e= Integer.parseInt(st.nextToken()); //간선의 갯수
		int p= Integer.parseInt(st.nextToken()); //건우의 위치 
		
		
		//간선 연결 정보 구현 
		map = new int[v][v];
		while(e-->0) {
			st= new StringTokenizer(br.readLine(), " "); 
			int a= Integer.parseInt(st.nextToken())-1; 
			int b= Integer.parseInt(st.nextToken())-1;
			int c= Integer.parseInt(st.nextToken()); 
			map[a][b]=map[b][a]=c;
		}
		int masan = dijkstra(0, v-1); //출발지 → 마산 (민준) 
		int gunwoo = dijkstra(0, p-1); //출발지 → 건우 
		int gunwoo_masan = dijkstra(p-1, v-1); //건우 → 마산
        
		if(masan == gunwoo+gunwoo_masan) System.out.println("SAVE HIM");
		else System.out.println("GOOD BYE");

	}//end of main 

	/*다익스트라 구현하기*/
	private static int dijkstra(int start, int end) {
		int dis[] = new int[v]; // 출발지로부터 도착지까지의 최단 거리 구하기 
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[start] = 0; 
		
		boolean check[] = new boolean[v]; //해당 정점을 거쳐가는 경로 탐색했는지 확인 여부 
		PriorityQueue<Node> que = new PriorityQueue<>(); 
		
		que.add(new Node(start, 0)); 
		while(!que.isEmpty()) {
			Node now= que.poll(); 
			int num = now.node_num;
			int weight = now.weight; 
			
			if(check[num]) continue; 
			check[num] = true;
			
			for(int i=0; i<v; i++) {
				//now 정점과 인접해 있는 정점
				if(map[num][i]!=0) {
					//새로운 값으로 갱신되면 , 
					if(dis[i] > weight+map[num][i]) {
						dis[i] = weight+map[num][i];
						que.add(new Node(i, dis[i])); 
					}
				}
			}
		}
		return dis[end]; 
	}
}//end of class