백준 11779번(JAVA)

이번 문제는 다익스트라 알고리즘에다가 되추적까지 해줘야 하는 문제다.

문제의 조건에는 안나와있지만 정점은 1번부터n번이다.

기본적으로 다익스트라와 동일하다.

단, 되추적을 위해 int[] before 배열을 선언한다

예를들어 최단거리 경로가 1번에서 3번으로 가기위한 최단 경로가 1->2->3일경우

before[3]=2, before[2]=1을 집어넣는다.

되추적은 일단 index를 end로 잡는다

그리고 루프를 돌면서 index를 스택에 넣고 index=before[index] 실시하고 count값을 증가시켜준다.

만약 index가 start가면 루프를 깬다.

count값을 출력하고 stack이 빌 때까지 계속 출력해주면 된다.

stack에는 처음에 index를 집어넣으면 end가 들어가고 마지막에는 start가 들어간다.

stack은 선입후출이기에 빌 때까지 출력하면 start가 가장 먼저 출력되고 end가 마지막에 출력된다.

아, before값은 다익스트라를 실시하며 거리값을 갱신할 때 같이 갱신한다.

 

소스코드

import java.util.*;
import java.io.*;
class Node implements Comparable<Node>
{
	int vertex;
	int weight;
	public 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));
		int n=Integer.parseInt(br.readLine());
		int m=Integer.parseInt(br.readLine());
		int[] before=new int[n+1];//되추적을 위한 배열
		boolean[] visited=new boolean[n+1];//방문했는지 알아보는 배열
		int[] dis=new int[n+1];//거리 배열
		Arrays.fill(dis, Integer.MAX_VALUE);//거리는 일단 가장 큰값으로 초기화 시켜둔다.
		ArrayList<Node>[] 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]);
		PriorityQueue<Node> q=new PriorityQueue<Node>();
		q.add(new Node(start,0));
		dis[start]=0;
		int count=1;//몇개인지 세기 위함이다
		while(!q.isEmpty())
		{
			Node temp=q.poll();
			int v=temp.vertex;
			if(!visited[v])
			{
				for(int i=0;i<map[v].size();i++)
				{
					int next=map[v].get(i).vertex;
					if(!visited[next]&&dis[next]>dis[v]+map[v].get(i).weight)
					{
						dis[next]=dis[v]+map[v].get(i).weight;
						q.add(new Node(next,dis[next]));
						before[next]=v;
					}
						
				}
			}
			visited[v]=true;//마지막은 방문 처리
			
		}
		System.out.println(dis[end]);
		Stack<Integer> result=new Stack<Integer>();//가장 처음에 들어간 end는 가장 나중에 출력되고 start점이 가장 먼저 출력된다
		int index=end;//end에서 시작해서 되추적 시작
		while(true)
		{
			result.push(index);
			if(index==start)//시작점에 도착했으면
			{
				break;
			}
			index=before[index];//되추적 실시
			count++;//방문한 갯수 증가
		}
		System.out.println(count);//몇개인지 출력
		while(!result.isEmpty())//스택이 빌 때까지 계속 출력, 시작은 start,끝은 end가 나온다
		{
			System.out.print(result.pop()+" ");
		}
	}
}

댓글 및 지적은 언제든지 환영입니다~!

글이 마음에 들었다면 왼쪽 이미지를 눌러서 후원 부탁드립니다><