백준 1753번 :: 최단경로 (Java)

문제 설명

백준 1753번: 최단경로 (Gold 5)

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

문제 풀이

1. V개의 정점에 대한 E개의 간선 정보를 담을 우선순위 큐 배열을 만든다.
2. 각 정점마다 가중치가 적은 순으로 간선 정보를 저장한다.
3. 다익스트라 알고리즘을 이용하여 시작점부터 다른 모든 정점으로 가는 최단 경로를 구한다.
4. 각 정점에 대해 최단 경로가 존재하면 그 값을, 존재하지 않으면 INF를 출력한다.

소스 코드

소스 코드 링크

static class Node implements Comparable<Node> {
	int to, weight;
	public Node(int to, int weight) {
		this.to = to;
		this.weight = weight;
	}
	@Override
	public int compareTo(Node o) {
		return this.weight-o.weight;
	}
}

public static void main(String[] args) throws IOException {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(in.readLine());
	StringBuilder sb = new StringBuilder();
	
	int V = Integer.parseInt(st.nextToken()); // 정점의 개수
	int E = Integer.parseInt(st.nextToken()); // 간선의 개수
	int start = Integer.parseInt(in.readLine()); // 시작정점의 번호
	
	// 각 간선에 대한 정보
	PriorityQueue<Node>[] adj = new PriorityQueue[V+1];
	for (int i = 1; i <= V; i++) {
		adj[i] = new PriorityQueue<Node>();
	}
	for (int i = 0; i < E; i++) {
		st = new StringTokenizer(in.readLine());
		int u = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		adj[u].add(new Node(v, w));
	}
	
	// 시작점에서 다른 정점으로의 최단 경로 구하기
	int[] distance = new int[V+1];
	Arrays.fill(distance, -1);
	distance[start] = 0; // 시작점 0 표시
	
	// 방문할 수 있는 곳 모두 가보기
	while (!adj[start].isEmpty()) {
		Node tmp = adj[start].poll();
		int to = tmp.to;
		int weight = tmp.weight;
		// 이미 방문한 곳은 지나침
		if (distance[to] != -1) continue;
		// 최단 경로 갱신 및 경유 했을 때 가중치 저장
		distance[to] = weight;
		for (Node n : adj[to]) {
			adj[start].add(new Node(n.to, n.weight+weight));
		}
	}
	for (int i = 1; i <= V; i++) {
		sb.append(distance[i] == -1 ? "INF" : distance[i]).append("\n");
	}
	System.out.println(sb.toString());
}

느낀 점

다익스트라 알고리즘만 제대로 알고 있으면 우선순위 큐를 이용해서 쉽게 풀 수 있는 문제였지만 이걸 처음 풀었을 때는 다익스트라에 대해 제대로 이해하지 못해서 그런가? 인접 행렬, 인접 리스트 말고 우선순위 큐를 쓰려니까 어렵게 느껴져서 못풀었다😵

근데 꽤 지나서 다시 풀어보니까 풀리네...! 이제 내 자신이 다익스트라에 대해서 좀 이해했나?ㅎ 아니면 우선순위 큐를 이전보다 더 많이 써봐서 이제 좀 쓸 줄 알게 된 건가( ◠‿◠ )? 뭐든 내 실력이 더 나아져서 그런거라면 상관 없지 뭐~~ 이렇게 계속 푸는 게 도움이 되긴 하나보다! 앞으로도 힘내자🔥