[알고리즘] 최소비용 구하기 (백준 1916번)

1916번: 최소비용 구하기

 한 시작점에서 나머지 노드까지의 최소 거리를 구하는, 전형적인 다익스트라 문제다. 사실 다익스트라 문제는 이번이 처음 풀어보는데 생각보다 시간이 오래걸렸다. 계속 8%에서 넘어가질 않아서 한참 고민하고 있었는데 알고 보니 버스는 단방향인데 나는 양방향으로 생각하고 문제를 풀었다....

 

Solution

1. dist 배열에서 시작점 dist[start] = 0이고 나머지는 무한대로 초기화한다.
2. 각 노드의 edge 정보들을 저장해놓는다. (인접리스트)
3. queue에 시작점 start를 넣는다.
   1. 현재 노드에 연결된 정점들의 최단 거리를 갱신한다.
   2. 아직 방문하지 않은 노드 중 최소 거리를 가지는 노드를 queue에 넣는다.
   3. 만약 모든 노드를 방문했다면 0을 반환한다.

그리고 생각보다 시간이 오래 걸려서 이것저것 바꾸어 보았는데 입력 데이터를 받아서 파싱할 때, split이 아닌 Stringtokenizer를 쓰니 속도가 훨씬 빨라지고 메모리 사용량도 많이 줄었다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int V, E;
	static int start, finish;
	static int dist[];
	static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
	static boolean visited[];

	public static void solution() throws Exception
	{
		V = Integer.parseInt(br.readLine());
		E = Integer.parseInt(br.readLine());

		visited = new boolean[V+1];

		for(int i = 0;i <= V;i++)
			graph.add(new ArrayList<>());

		for(int i = 0;i < E;i++)
		{
			StringTokenizer strtok = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(strtok.nextToken());
			int to = Integer.parseInt(strtok.nextToken());
			int weight = Integer.parseInt(strtok.nextToken());

			graph.get(from).add(new Edge(from, to, weight));
		}

		StringTokenizer strtok = new StringTokenizer(br.readLine());
		start = Integer.parseInt(strtok.nextToken());
		finish = Integer.parseInt(strtok.nextToken());

		dist = new int[V+1];

		//시작점만 0으로, 나머지까지 거리는 무한대
		for(int i = 0; i <= V;i++)
		{
			if(i != start)
				dist[i] = Integer.MAX_VALUE;
		}

		bw.write(dijkstra()+"");
	}

	static int dijkstra()
	{
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);

		visited[start] = true;

		while (!queue.isEmpty())
		{
			int now = queue.poll();

			//now에서 도달 가능한 정점들의 최단 거리 갱신
			for(int i = 0;i < graph.get(now).size();i++)
			{
				Edge e = graph.get(now).get(i);

				//이미 방문한 애들은 무조건 최단거리 (음수가 없다는 가정하의 다익스트라 특징)
				if(!visited[e.to])
					dist[e.to] = Math.min(dist[e.to], dist[now] + e.weight);
			}

			int next = getMinIndex();

			if(next != 0)
			{
				visited[next] = true;
				queue.offer(next);
			}
		}

		return dist[finish];
	}

	//만약 더이상 방문할 수 있는 노드가 없으면 0반환
	static int getMinIndex()
	{
		int min_index = 0;

		for(int i = 1;i <= V;i++)
		{
			if(!visited[i] && dist[min_index] > dist[i])
				min_index = i;
		}
		return min_index;
	}


	static class Edge{
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
	}
	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}