백준 1504번(JAVA)

 

다익스트라 알고리즘을 응용하는 문제이다.

말이 응용이지 그냥 다익스트라를 3번 써주면 된다.

우선 기본적인 다익스트라 알고리즘을 알아야 한다.

혹시 모르는 분들은 이전 포스팅을 참고하길 바란다.

2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA)

백준 1916번(JAVA)

문제는 간단하다. 1번부터 시작해서 N번까지의 최단경로를 구하라.

단, 특정 두 정점을 거쳐야 한다.

특정정점을 A,B라고 하면

2가지 경로가 있다

1번 -> A->B->N번

1번 ->B->A->N번

• 1번을 시작으로 다익스트라를 하면 1번에서 A,1번에서 B까지의 최단거리를 알 수 있다
• 그다음 다 초기화해주고 A에서 다익스트라를 하면 A에서 B,A에서 N번까지의 최단거리를 알 수 있다.
• 다시 초기화해주고 B에서 다익스트라를 하면 B에서A(위에서 구한 A에서 B까지랑 똑같은 값),B에서 N번까지의 최단거리를 알 수있다.

위와 같이 3번 다익스트라를 실행하고 각 경로에 해당하는 값을 더해줘서 2가지 경로를 서로 비교한다

이 때 만약 2가지 경로의 값이 모두 100만 보다 크다면 경로가 없다는 뜻이므로 -1을 출력한다.

왜 하필 100만인가? 경로값은 1000이하고 정점은 800개이하가 문제의 조건이다.

어떻게 해도 거리는 80만은 못넘겨서 걍 100만으로 잡았다. 만약 경로가 없다면 Integer.MAX_VALUE가 더해진다.

이제 2가지 경로를 비교해서 작은값을 출력한다.

아래는 전체 소스코드다

소스 코드

import java.util.*;
import java.io.*;

class Node implements Comparable<Node>
{
	int vertex;
	int weight;
	Node(int vertex,int weight)
	{
		this.vertex=vertex;
		this.weight=weight;
	}
	@Override
	public int compareTo(Node o)
	{
		return weight-o.weight;
	}//우선순위 큐에 넣을때 간선이 짧은게 가장 큰 우선순위를 갖도록 구현
}
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] s=br.readLine().split(" ");
		int N=Integer.parseInt(s[0]);
		int M=Integer.parseInt(s[1]);
		ArrayList<Node>[] arr=new ArrayList[N+1];
		for(int i=1;i<=N;i++)
		{
			arr[i]=new ArrayList<Node>();
		}
		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]);
			arr[a].add(new Node(b,c));
			arr[b].add(new Node(a,c));//양방향 그래프이기 때문에
		}
		s=br.readLine().split(" ");
		int des1=Integer.parseInt(s[0]);//지나야 되는 두 정점중 첫번째
		int des2=Integer.parseInt(s[1]);//지나야 되는 두 정점중 두번째
		boolean[] visited=new boolean[N+1];
		int[] dis=new int[N+1];
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[1]=0;
		PriorityQueue<Node> q=new PriorityQueue<Node>();
		q.add(new Node(1,0));//시작점 1에서부터 시작
		while(!q.isEmpty())//시작점에서 다익스트라를 실시한다.
		{
			Node temp=q.poll();
			int v=temp.vertex;
			if(!visited[v])
			{
				for(int i=0;i<arr[v].size();i++)
				{
					Node next=arr[v].get(i);
					if(!visited[next.vertex]&&dis[next.vertex]>dis[v]+next.weight)
					{
						dis[next.vertex]=dis[v]+next.weight;
						q.add(new Node(next.vertex,dis[next.vertex]));
					}
				}
			}
			visited[v]=true;
		}
		int route1_1=dis[des1];//지나야되는 두 정점중 시작점에서부터 첫번째 정점까지의 거리
		int route2_1=dis[des2];//지나야되는 두 정점중 시작점에서부터 두번째 정점까지의 거리
		Arrays.fill(visited, false);
		Arrays.fill(dis, Integer.MAX_VALUE);
		q.clear();
		q.add(new Node(des1,0));//지나야되는 두 정점중 첫번째부터 시작
		dis[des1]=0;
		while(!q.isEmpty())
		{
			Node temp=q.poll();
			int v=temp.vertex;
			if(!visited[v])
			{
				for(int i=0;i<arr[v].size();i++)
				{
					Node next=arr[v].get(i);
					if(!visited[next.vertex]&&dis[next.vertex]>dis[v]+next.weight)
					{
						dis[next.vertex]=dis[v]+next.weight;
						q.add(new Node(next.vertex,dis[next.vertex]));
					}
				}
			}
			visited[v]=true;
		}
		int between=dis[des2];//지나야 되는 두 정점사이의 거리
		int route2_2=dis[N];//des1에서 최종 목적지 N까지의 거리
		Arrays.fill(visited, false);
		Arrays.fill(dis, Integer.MAX_VALUE);
		q.clear();
		q.add(new Node(des2,0));
		dis[des2]=0;
		while(!q.isEmpty())
		{
			Node temp=q.poll();
			int v=temp.vertex;
			if(!visited[v])
			{
				for(int i=0;i<arr[v].size();i++)
				{
					Node next=arr[v].get(i);
					if(!visited[next.vertex]&&dis[next.vertex]>dis[v]+next.weight)
					{
						dis[next.vertex]=dis[v]+next.weight;
						q.add(new Node(next.vertex,dis[next.vertex]));
					}
				}
			}
			visited[v]=true;
		}
		int route1_2=dis[N];//des2에서 최종 목적지 N까지의 거리
		long route1=(long)(route1_1+route1_2+between);
		long route2=(long)(route2_1+route2_2+between);
		//long으로 바꾼것은 Integer.MAX_VALUE가 들어가 있으면 Int형을 넘어서 그렇다.
		if(route1>=1000000&&route2>=1000000)//만약에 2가지 루트로 가는 길이 없다면...
		{
			System.out.println("-1");
		}
		else
		{
			System.out.println(Math.min(route1, route2));
		}
	}
}

댓글과 지적은 언제든지 환영입니다.

제 글이 마음에 들었다면 아래 버튼을 클릭해서 후원부탁드립니다~!><