백준 1916번(JAVA)

다익스트라 알고리즘을 이용해 푸는 문제다

저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다.

다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방식으로 푸는 DP문제 같다.

내가 생각하는 핵심은 딱 4가지다.

• 출발지에서의 거리가 가장짧은것이 우선순위가 높게 우선순위큐를 구현해준다. 이때 우선순위 큐는 정수형이 아닌 Node객체를 넣을 수 있게 구현한다.
• 거리 배열을 따로만들며. 시작점은 0으로 나머지는 가장큰수로 초기화해준다
• 시작점에서 시작해서 BFS를 실시한다.
• BFS시 정점A에서 B로 갈때 만약 B가 방문된적없고 dis[B]>dis[A]+A에서B로가는 가중치 일경우 dis[B]=dis[A]+A에서 B로 가는 가중치 로 갱신해주고 우선순위 큐에 B정점과,dis[B]를 넣어준다.

위의 4가지를 머리에 새기고 아래와 같이 소스 코드를 작성했다. 

소스 코드

import java.util.*;
import java.io.*;
class Node implements Comparable<Node>{
	int V;
	int weight;
	public Node(int V,int weight)
	{
		this.V=V;
		this.weight=weight;
	}	
	@Override
	public int compareTo(Node o)
	{
		return weight-o.weight;
	}//우선순위 큐에 넣을 때 간선길이가 짧은게 가장 큰 우선순위를 갖도록 구현
}
public class 백준_1916번 {

	public static boolean[] visited;
	public static ArrayList<Node>[] map;
	public static int[] dis;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		int M=Integer.parseInt(br.readLine());
		visited=new boolean[N+1];//방문했는지 확인하는용
		dis=new int[N+1];//거리 배열
		map=new ArrayList[N+1];//그래프
		for(int i=1;i<=N;i++)
		{
			map[i]=new ArrayList<Node>();
		}
		String[] s;
		for(int i=0;i<M;i++)
		{
			s=br.readLine().split(" ");
			int a=Integer.parseInt(s[0]);
			int b=Integer.parseInt(s[1]);
			int c=Integer.parseInt(s[2]);
			map[a].add(new Node(b,c));//유향그래프이다
		}
		s=br.readLine().split(" ");
		int start=Integer.parseInt(s[0]);
		int end=Integer.parseInt(s[1]);
		Arrays.fill(dis, Integer.MAX_VALUE);//일단 모든 거리는 가장큰수로 초기화
		dis[start]=0;//시작점만 0으로
		PriorityQueue<Node> q=new PriorityQueue<>();
		q.offer(new Node(start,0));//시작점과 거리 0 넣는다
		while(!q.isEmpty())
		{
			Node temp=q.poll();
			if(!visited[temp.V])//방문된적이없다면
			{
				visited[temp.V]=true;//방문처리를 해주고
				for(int i=0;i<map[temp.V].size();i++)//해당 노드와 연결된걸 모두 확인한다
				{
					Node next=map[temp.V].get(i);
					if(!visited[next.V]&&dis[next.V]>next.weight+dis[temp.V])//방문된적없고 거리값이 갱신되야되면
					{
						dis[next.V]=next.weight+dis[temp.V];//거리값 갱신해주고
						q.add(new Node(next.V,dis[next.V]));//우선순위큐에 넣어준다.
					}
				}
			}
		}
		System.out.println(dis[end]);//목적지까지의 거리 출력
	}
}

 

지적과 댓글,질문은 언제든지 환영입니다~!

글이 마음에 들었다면 위 버튼을 클릭해서 후원해주세요><