백준 20007 <떡 돌리기>

성현이 집에서 모든 집의 가장 가까운 거리를 찾는 것이 필요한 문제이다.

 

즉 다익스트라 알고리즘을 사용하는 문제이다. 다익스트라 알고리즘을 사용하면서 마을마다 가장 가까운 거리를 기억하고 그 정보를 이용해 며칠이 걸리는지를 푸는 문제이다.

 

 문제 해결

1. 다익스트라 알고리즘을 이용해서 각각의 마을의 가까운 거리를 큐에 담아준다.
2. 큐에서 꺼내면서 현재 이동할수 있는 거리보다 작으면 하루를 더해준다.
3. 예외사항의 경우는 성현이 집에서 모든 집을 방문할 수 없을 때와 성현이가 왕복할 수 있는 거리보다 거리가 더 멀 때 -1을 출력한다.

문제를 잘읽자.

 

다익스트라 알고리즘이다. 이를 통해서 우선순위 큐로 인해 거리가 작은 순서대로 정렬되기 때문에 방문하지 않았을 경우 q에 담으면 거리가 가까운 순으로 정렬된다.

 

 

예외사항이다. q 사이즈가 n-1이 아니라는 것은 모든 마을을 돌 수 없다는 것이다.

 

다음은 최소 일수를 구하는 공식이다. 예외사항을 반드시 기억하자.

 

문제가 생각보다 어렵지는 않았지만 생각이 필요한 문제. 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static class Point implements Comparable<Point>{
		int x;
		int y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;//거리
		}
		@Override
		public int compareTo(Point o) {
			// TODO Auto-generated method stub
			return this.y-o.y;
		}
		
		
	}
	
	static boolean visit[];
	static ArrayList<Point> num[];
	static int n,m,x,y,t=1;
	static Queue<Integer> q;  
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader (System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		x=Integer.parseInt(st.nextToken());
		y=Integer.parseInt(st.nextToken());
		num=new ArrayList[n+1];
		visit=new boolean[n+1];
		q=new LinkedList<Integer>();
		for(int i=0;i<=n;i++) {
			num[i]=new ArrayList<Point>();
		}
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int f=Integer.parseInt(st.nextToken());
			int s=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			num[f].add(new Point(s,d));
			num[s].add(new Point(f,d));
		}
		line();
		if(q.size()!=n-1) {
			System.out.println(-1);
		}
		else {
			sum();
			System.out.println(t);
		}
		
	}
	private static void sum() {
		// TODO Auto-generated method stub
		int sum=x;
		while(!q.isEmpty()) {
			int d=q.remove();
			if(2*d>x) {
				t=-1;
				return;
			}
			else {
				if(2*d<=sum) {
					sum-=(2*d);
				}
				else {
					sum=x;
					sum-=(2*d);
					t++;
				}
			}
		}
	}
	private static void line() {
		// TODO Auto-generated method stub
		PriorityQueue<Point> pq=new PriorityQueue<Point>();
		for(int i=0;i<num[y].size();i++) {
			pq.add(num[y].get(i));
		}
		visit[y]=true;
		while(!pq.isEmpty()) {
			Point next=pq.remove();
			if(visit[next.x]) {
				continue;
			}
			visit[next.x]=true;
			q.add(next.y);
			for(int i=0;i<num[next.x].size();i++) {
				Point nex=num[next.x].get(i);
				if(visit[nex.x])
					continue;
				pq.add(new Point(nex.x,next.y+nex.y));
			}
		}
	}

}