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

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

1916번: 최소비용 구하기

코태기 3일만에 종료,,

---

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

▶ N개의 도시가 존재, 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스 존재

▶ A번째 도시에서 B번째 도시까지 가는데 버스의 최소 비용 출력

▶ Input : 첫째 줄에 도시의 개수 N, 둘째 줄에 버스의 개수 M, 다음 M개의 줄에 버스의 출발,도착, 비용 입력

                 마지막 줄에 출발점의 도시번호와 도착점의 도시 번호 입력

▶ Output : 출발 도시에서 도착 도시까지 가는데 드는 최소 비용 출력

---

◈ Input - 1

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

◈ Output - 1

4

---

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

▶ 최소 비용 == 다잌스트라

▶ 도시의 정보를 인접리스트로 저장, Node 클래스를 구현하여 시작 노드(도시), 끝 노드(도시), 가중치(비용) 저장

▶ 다익스트라 알고리즘 활용 == 목표 지점까지 최소 가중치 값 찾기

    1. 노드의 크기만큼의 임의의 배열 narrDaijk을 설정

      ( narrDaijk[i] == i 지점까지 각 노드의 최소 비용이 드는 경로)

    2. 모든 배열 값을 Integer.max_value로 설정, 최초 탐색 번호인 도시의 시작점만 해당 배열의 값으로 설정

         (0번의 도둑루피 값을 들고 시작)

    3. 현재 narrDaijk 값들 중 방문처리가 안되있으며 가장 작은 값을 찾은 후 해당 인덱스 저장

    4. 해당 인덱스는 방문 처리 ( == true로 설정)

    5. 해당 인덱스의 인접리스트를 탐색하여 연결된 노드들을 탐색

    6. narrDaijk[다음노드번호]  와  narrDaijk[현재노드] + 현재 노드의 다음노드까지의 거리를 비교,

         둘 중에 작은 값을 narrDaijk[다음노드번호]에 저장

    7. 3~6번을 도착점 번호의 노드가 true 처리 될 때 까지 반복

    8. narrDaijk[도착점번호] 값 출력

---

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.Arrays;
import java.util.StringTokenizer;

class Node {
	int m_nEnd;
	int m_nDistance;

	public Node() {
		// TODO Auto-generated constructor stub
	}

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

public class Main {
	static int N, M;
	static ArrayList<Node>[] listNodes;

	public static void main(String[] args) throws IOException {
	
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		// 노드 입력 받고

		N = Integer.parseInt(bReader.readLine());
		M = Integer.parseInt(bReader.readLine());

		listNodes = new ArrayList[N + 1];
		for (int i = 0; i < N + 1; i++) {
			listNodes[i] = new ArrayList<>();
		}

		// 인접 리스트로 시작, 끝 노드 + 가중치 저장
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			int nStart = Integer.parseInt(st.nextToken());
			int nEnd = Integer.parseInt(st.nextToken());
			int nDistance = Integer.parseInt(st.nextToken());

			listNodes[nStart].add(new Node(nEnd, nDistance));
		}

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		int nFirst = Integer.parseInt(st.nextToken());
		int nEnd = Integer.parseInt(st.nextToken());

		bWriter.write(String.valueOf(Daijkstra(nFirst, nEnd)));
		bWriter.close();
	}

	private static int Daijkstra(int nFirst, int nEnd) {
		// TODO Auto-generated method stub
		int[] narrDaijk = new int[N + 1];
		boolean[] barrDaijk = new boolean[N + 1];
		
		Arrays.fill(narrDaijk, Integer.MAX_VALUE);
		narrDaijk[nFirst] = 0;
		
		for (int i = 1; i <= N; i++) {
			int nMin = Integer.MAX_VALUE;
			int nIndex = -1;
			
			for(int j = 1; j <= N; j++) {
				if(nMin > narrDaijk[j] && !barrDaijk[j]) {
					nMin = narrDaijk[j];
					nIndex = j;
				}
			}
			
			if(nIndex == -1)
				break;
			
			barrDaijk[nIndex] = true;
			
			for(int j = 0; j < listNodes[nIndex].size(); j++) {
				int nNextNode = listNodes[nIndex].get(j).m_nEnd;
				int nDistance = listNodes[nIndex].get(j).m_nDistance;
				
				if(!barrDaijk[nNextNode] && narrDaijk[nNextNode] > narrDaijk[nIndex] + nDistance)
					narrDaijk[nNextNode] = narrDaijk[nIndex] + nDistance;
			}
			
			if(nIndex == nEnd)
				return narrDaijk[nEnd];
		}

		return -1;
	}
}

---

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