[백준] 떡 돌리기 2007 [JAVA]

출처 :www.acmicpc.net/problem/20007 

20007번: 떡 돌리기

문제

군인인 성현이는 전역 후에 새 집으로 이사를 갔다. 주변 이웃과 친하게 지내고 싶은 마음에 이웃집에 떡을 돌리기로 했다. 떡은 한번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다. 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 또 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐한다. N-1개의 이웃집 모두에게 떡을 돌리기 위해서는 최소 며칠이 소요될 것인가.

입력

첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)

두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주어진다. (0 ≤ A,B < N, 1 ≤ C ≤ 10,000) 단 A와 B는 서로 다른 수이다.

단, A집과 B집을 연결하는 도로는 유일하다.

출력

성현이의 집을 Y 라고 할 때, 이웃집 모두에 떡을 돌리기 위한 최소 일을 출력한다. 만약 모두 방문할수 없으면 -1을 출력한다.

풀이 방법

 1. 성현이의 집을 출발점으로 다익스트라 알고리즘

 2. 각 집마다의 최소거리를 갱신하자.

 3. 갱신된 집을 가까운 순서대로 정렬

 4. 한곳 씩 방문하면서, answer 증가 하되 왕복거리가 X를 넘어서면 갈 수 없음 

코드

package 알고리즘스터디문제;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 떡돌리기_20007 {

	static int N, M, X, Y;
	static boolean[] visited;
	static ArrayList<home>[] arr; // 연결 유무를 판단할 어레이 리스트
	static PriorityQueue<home> pq = new PriorityQueue<>(); // 우선순위 큐, 성현이의 집에서 출발하면서 가까운 거리순서 대로 활용할 예정
	static int[] dist;
	static final int max = Integer.MAX_VALUE;
	static int answer = 1;

	public static class home implements Comparable<home> {
		int number, dist;

		public home(int number, int dist) {
			super();
			this.number = number;
			this.dist = dist;
		}

		@Override
		public int compareTo(home o) {
			// TODO Auto-generated method stub
			return this.dist - o.dist;
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt(); // 성현이의 집을 포함한 총 N개의 집
		M = sc.nextInt(); // 각 집 간에 연결될 곳
		X = sc.nextInt(); // 하루에 X보다 멀지 않은 곳 걸어갈 수 있다.
		Y = sc.nextInt(); // 성현이의 집

		// 연결 리스트 관리
		arr = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			arr[i] = new ArrayList<>();
		}
		visited = new boolean[N];
		dist = new int[N];

		for (int i = 0; i < M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int dist = sc.nextInt();
			arr[from].add(new home(to, dist)); // 양방향 연결
			arr[to].add(new home(from, dist));
		}

		// 1. 우선순위 큐로 성현이 집 시작으로부터 가까운 거리로 걸리는 거리 저장 해두기
		dijkstra();

		// 2. 가까운 순서대로 정렬하기
		Arrays.sort(dist);

		//print();

		// 3. 하나씩 방문하면서 day 증가
		visit();
		System.out.println(answer);
	}

	private static void print() {
		// TODO Auto-generated method stub
		for (int i = 0; i < dist.length; i++) {
			System.out.print(dist[i] + " ");
		}
	}

	private static void visit() {
		// TODO Auto-generated method stub
		int totaldist =0;
		for (int i = 0; i < dist.length; i++) {
			// 가려고 하는 곳이 왕복거리를 포함해서 X안에 갈 수 없다면!? NO answer
			if ( dist[i]*2 > X ) {
				answer = -1;
				break;
			}
			// 방문한 왕복 거리 계속 더하다가.
			totaldist += dist[i]*2;
			
			// 그 거리가 X보다 크다면? == 하루안에는 못가잖아. 그러니까, 하루 더 추가해주고 totaldist는 현재 방문한 거리의 값으로 바꿔주자.
			if ( totaldist > X ) {
				answer++;
				totaldist = dist[i]*2;;
			}
			
		}

	}

	// 1.성현이의 집을 출발지로 가능한 모든 집 간의 거리를 최소값으로 정렬하자.
	private static void dijkstra() {
		Arrays.fill(dist, max);
		dist[Y] = 0; // 성현이의 집은 거리 0 이니까

		// 성현이의 집 큐에 먼저 넣기.
		pq.add(new home(Y, 0));

		while (!pq.isEmpty()) {

			// 1. 큐 꺼내고
			home cur = pq.poll();
			int curPos = cur.number;
			int curdist = cur.dist;

			// 2. 거기에서 연결된 모든 노드들 방문하면서 성현이의 집으로부터의 거리를 갱신하자.
			// 2-1) 여기에서 방문했다고 ㄹㅇ방문한거 아님
			for (int i = 0; i < arr[curPos].size(); i++) {
				int target = arr[curPos].get(i).number;
				int target_dist = arr[curPos].get(i).dist;

				// 1) 방문 하지 않았고, 이전 까지 거쳐서 걸린 거리가 기존에 저장된 값보다 작다면 갱신해주기 ==> 만약 작지 않으면 갱신할 필요 없음
				// 2) 그리고 우선순위 큐에 넣어주자.
				if (visited[target] == false && dist[target] > target_dist + curdist) {
					dist[target] = target_dist + curdist; // 갱신
					pq.add(new home(target, dist[target]));

				}

			}
			// 3. 꺼냈다. = 방문 처리
			visited[curPos] = true;

		}

	}
}