[백준] 1916 : 최소비용 구하기 - JAVA

내 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
public static ArrayList<Edge> list[];
public static boolean[] visited;
public static int[] distance;
public static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		list = new ArrayList[N+1];
		distance = new int[N+1];
		visited = new boolean[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<Edge>();
			distance[i] = Integer.MAX_VALUE;
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			list[start].add(new Edge(end, value));
		}
		st = new StringTokenizer(br.readLine());
		int here = Integer.parseInt(st.nextToken());
		int goal= Integer.parseInt(st.nextToken());
		
		distance[here] =0;
		q.add(new Edge(here, 0));
		dijkstra(here, goal);
		System.out.println(distance[goal]);
	}
	
	public static void dijkstra(int here, int goal) {	
		while(!q.isEmpty()) {
			Edge e = q.poll();
			int now = e.vertex;
			if(visited[now]) continue;
			visited[now] = true;
			for(int k=0; k<list[now].size(); k++) {
				Edge temp = list[now].get(k);
				int next = temp.vertex;
				int value = temp.value;
				if(distance[next] > value + distance[now]) {
					distance[next] = value + distance[now];
					q.add(new Edge(next, distance[next]));
				}
			}
			if(visited[goal]) return;
		}	
	}
}
class Edge implements Comparable<Edge> {
	int vertex, value;
	
	public Edge(int vertex, int value) {
		this.vertex = vertex;
		this.value = value;
	}
	
	@Override
	public int compareTo(Edge e) {
		if(this.value > e.value) return 1;
		else return -1;
	}
}

개선된 풀이

시간복잡도나 공간효율성측면보다는 코드를 조금 더 간결히 사용하는 방법으로 수정했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
public static ArrayList<Edge> list[];
public static boolean[] visited;
public static int[] distance;
public static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		list = new ArrayList[N+1];
		distance = new int[N+1];
		visited = new boolean[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<Edge>();
		}
		Arrays.fill(distance, Integer.MAX_VALUE);
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			list[start].add(new Edge(end, value));
		}
		st = new StringTokenizer(br.readLine());
		int here = Integer.parseInt(st.nextToken());
		int goal= Integer.parseInt(st.nextToken());
		distance[here] =0;
		q.add(new Edge(here, 0));
		dijkstra(here, goal);
		System.out.println(distance[goal]);
	}
	public static void dijkstra(int here, int goal) {	
		while(!q.isEmpty()) {
			Edge e = q.poll();
			int now = e.vertex;
			if(visited[now]) continue;
			visited[now] = true;
			for(Edge temp : list[now]) {
				int next = temp.vertex;
				int value = temp.value;
				if(distance[next] > value + distance[now]) {
					distance[next] = value + distance[now];
					q.add(new Edge(next, distance[next]));
				}
			}
			if(visited[goal]) return;
		}	
	}
}

class Edge implements Comparable<Edge> {
	int vertex, value;
	
	public Edge(int vertex, int value) {
		this.vertex = vertex;
		this.value = value;
	}
	
	@Override
	public int compareTo(Edge e) {
		if(this.value > e.value) return 1;
		else return -1;
	}
}

1. 이전에는 반복문을 돌며 distance[i] = Integer.MAX_VALUE;이렇게 원소 하나씩 접근해 값을 최대값으로 초기화 했었다.
   -> Arrays.fill(distance, Integer.MAX_VALUE); : Arrays.fill() 메소드를 사용해 값을 채워넣었다.

2. for(int k=0; k<list[now].size(); k++) { Edge temp = list[now].get(k); ...} 이렇게 반복문을 구성했기때문에 반복 블록의 처음에 temp변수로 따로 받았다.
   -> for(Edge temp : list[now]) {} 향상된 for문을 사용해 한번에 해결했다.