[백준] 14284 간선 이어가기 2(JAVA)

1. 소요시간 : 20분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 그래프 이론, 다익스트라
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/14284
8. 푼 날짜 : 2023.03.25

1. 사용한 자료구조 & 알고리즘

다익스트라 알고리즘을 사용했다.

2. 풀이과정

그냥 다익스트라 알고리즘의 정의 그 자체인 문제였다.
플로이드-워셜 알고리즘을 사용할 필요가 없었다. 시작점과 끝점이 주어져 있었기 때문에 O(ElogV) 인 다익스트라 알고리즘을 사용.

3. 소스코드

import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
	int node;
	int cost;
	Node(int node,int cost){
		this.node=node;
		this.cost=cost;
	}
	@Override
	public int compareTo(Node o) {
		if(this.cost>o.cost)
			return 1;
		return -1;
	}
}

public class Main {

	static StringBuilder sb=new StringBuilder();

	static ArrayList<Node> graph[];
	static int INF=1000000000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		graph=new ArrayList[n+1];
		for(int i=1;i<graph.length;i++)
			graph[i]=new ArrayList<>();
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int node1=Integer.parseInt(st.nextToken());
			int node2=Integer.parseInt(st.nextToken());
			int cost=Integer.parseInt(st.nextToken());
			graph[node1].add(new Node(node2,cost));
			graph[node2].add(new Node(node1,cost));
		}
		st=new StringTokenizer(br.readLine());
		int s=Integer.parseInt(st.nextToken());
		int t=Integer.parseInt(st.nextToken());
		
		System.out.println(dijkstra(s,t));
		
		
	}
	public static int dijkstra(int start,int end) {
		PriorityQueue<Node> pq=new PriorityQueue<>();
		pq.add(new Node(start,0));
		boolean visited[]=new boolean[graph.length];
		int dist[]=new int[graph.length];
		Arrays.fill(dist,INF);
		dist[start]=0;
		while(!pq.isEmpty()) {
			
			int nowVertex=pq.poll().node;
			if(visited[nowVertex]) continue;
			visited[nowVertex]=true;
		
			for(Node next:graph[nowVertex]) {
				if(dist[next.node]>dist[nowVertex]+next.cost) {
					dist[next.node]=dist[nowVertex]+next.cost;
					pq.add(new Node(next.node,dist[next.node]));
				}
				
			}
			
			
			
		}
		
		return dist[end];
	}
}

4. 결과

5. 회고

다익스트라 알고리즘을 거의 1달 ? 만에 다시 써서
많이 까먹어가지고 좀 헤맸다.
벨만포드 알고리즘은 공부해야지 해야지 하고 넘긴지 좀 됐는데
다음주에 공부해볼 예정이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212