[골드4] 18223. 민준이와 마산 그리고 건우(Java)

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

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

본민준섭 크로스으~

---

※  문제를 요약하면 아래와 같습니다.

▶ 민준이는 고향인 1에서 마산 지점인 P로 이동을 계획

▶ 건우는 혼자 남겨진 상태에서 민준이에게 연락, 민준이는 가는 길에 건우가 있으면 도와주기 가넝 (양방향 그래프)

▶ 즉, 민준이가 건우를 도와주는 경로의 길이가 최단 경로의 길이보다 길어 지지 않는다면, 민준이는 반드시 건우를 도움

▶ Input : 첫번째 줄에 정점의 개수 V, 간선의 개수 E, 건우가 위치한 정점 P가 공백으로 구분되어 입력, 

                 이후 E개의 줄에 시작 지점, 다음 지점, 가중치가 차례대로 공백을 기준으로 입력

▶ Output : 최단 경로위에 건우가 있다면 "SAVE HIM", 없다면 "GOOD BYE" 출력

---

◈ Input - 1

6 7 4
1 2 1
1 3 1
2 3 10
3 4 1
3 5 2
4 5 1
5 6 1

◈ Output - 1

SAVE HIM

◈ Input - 2

4 3 3
1 2 1
2 3 1
2 4 1

◈ Output - 2

GOOD BYE

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 1번~V번 (최종지점) 까지의 최소 경로와 1번~P번(건우 지점), P번~V번까지의 최소 경로를 비교

▶ 1번~V번의 최소 경로 값이 더 작다면, "GOOD BYE"

     ( 건우를 들렸을 때 경로 값이 더 든다는건, 아쉽지만 최소 경로 위에 건우는 없다는 뜻)

▶  1번~P번(건우 지점), P번~V번과 값이 동일하다면 "SAVE HIM" 

     ( 다잌스트라 알고리즘 활용 시 동일 하다는 것 == 경로 위에 존재 )

▶ 위의 과정을 Daijkstra 알고리즘 활용하여 1번 ~V번 최소 경로, 1~P 최소경로 + P~1 의 최소 경로를 비교

       다잌스트라 풀이 과정은 아래에 작성된 것을 참고해주세요!

    : https://heih.tistory.com/120

[골드5] 1916. 최소 비용 구하기 (Java)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Node{
	int m_nNext;
	int m_nDistance;
	
	public Node(int m_nNext, int m_nDistance) {
		super();
		this.m_nNext = m_nNext;
		this.m_nDistance = m_nDistance;
	}
}

public class Main {
	static int V,E,P;
	static ArrayList<Node>[] listNode;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		P = Integer.parseInt(st.nextToken());
		
		// 인접 리스트 초기화
		listNode = new ArrayList[V+1];
		for(int i = 0 ; i < V+1; i++) {
			listNode[i] = new ArrayList<>();
		}
		
		// 인접 리스트에 저장
		for(int i = 0 ; i < E; i++) {
			st = new StringTokenizer(bReader.readLine());
			int nStart = Integer.parseInt(st.nextToken());
			int nNext = Integer.parseInt(st.nextToken());
			int nWeight = Integer.parseInt(st.nextToken());
			listNode[nStart].add(new Node(nNext, nWeight));
			listNode[nNext].add(new Node(nStart, nWeight));
		}
		
		// 다잌잌
		int nMinjoon = dijkstra(1, V);
		int nGunwoo = dijkstra(1,P) + dijkstra(P,V);
		
		String strResult = "SAVE HIM";
		if(nMinjoon != nGunwoo)
			strResult = "GOOD BYE";
		
		bWriter.write(strResult);
		bWriter.close();
	}

	private static int dijkstra(int nStart, int nEnd) {
		int[] narrDaijk = new int[V+1];
		boolean[] barrDaijk = new boolean[V+1];
		for(int i = 0; i <= V; i++)
			narrDaijk[i] = Integer.MAX_VALUE;
		
		narrDaijk[nStart] = 0;
		
		for(int i = 1; i <= V; i++) {
			int nIndex = -1;
			int nMin = Integer.MAX_VALUE;
			
			for(int j = 1; j <= V; j++) {
				if(!barrDaijk[j] && nMin > narrDaijk[j]) {
					nMin = narrDaijk[j];
					nIndex = j;
				}	
			}
			
			barrDaijk[nIndex] = true;
			
			if(barrDaijk[nEnd])
				return narrDaijk[nEnd];
			
			if(nIndex == -1)
				break;
			
			for(int j = 0; j < listNode[nIndex].size(); j++) {
				Node node = listNode[nIndex].get(j);
				if(barrDaijk[node.m_nNext])
					continue;
				
				if(narrDaijk[node.m_nNext] > narrDaijk[nIndex] + node.m_nDistance)
					narrDaijk[node.m_nNext] = narrDaijk[nIndex] + node.m_nDistance;
			}
		}
		
		return 0;
	}


}

---

Good Luck! (피드백 감사합니다!)