백준 | 20007번. 떡 돌리기 - 다익스트라 문풀

⬛ 백준 20007번. 떡 돌리기 - 다익스트라 문풀

https://www.acmicpc.net/problem/20007

20007번: 떡 돌리기

문제

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

집의 번호는 0번부터 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는 서로 다른 수이고, C는 정수이다.

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

출력

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

---

💚나의 풀이

• 일반적인 다익스트라 문제와 비슷하긴 하지만, 날짜를 구하기가 까다로웠다.
• 양방향 도로이므로, 왕복의 거리는 기존에 구해놓은 distance배열의 2배를 하면 된다.
• 문제를 읽어보면, 한 번에 하나씩의 떡만 배달할 수 있기 때문에 한 지점이라도 왕복거리가 X를 넘어가면 못 간다고 봐야 한다. → -1 출력
• 가장 까다로운 부분은 다익스트라롤 구해놓은 최단거리를 누적해서 더하다가 X 넘어가는 값 직전에 날짜 카운팅 업 처리하는 부분이었다.

package to_0901_3;

import java.util.*;
import java.util.Scanner;

/*20007번. 떡 돌리기 -다익스트라 문풀 */ 
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e = e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}

public class Main {
	static int N, M, X, Y;
	static ArrayList<ArrayList<Edge>> graph;
	static int[] distance;//거리용 배열 
	static boolean[] visited;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		N = kb.nextInt();//정점 개수 
		M = kb.nextInt(); //도로 개수
		X = kb.nextInt();//기준 거리 
		Y = kb.nextInt(); //출발 점 
		
		//초기화 
		graph = new ArrayList<>();
		distance = new int[N];
		Arrays.fill(distance, Integer.MAX_VALUE);
		visited =new boolean[N];
		
		for(int i=0; i<N; i++) {
			graph.add(new ArrayList<>());
		}
		//데이터 입력받기 
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int t = kb.nextInt();
			//양방향
			graph.get(a).add(new Edge(b, t));
			graph.get(b).add(new Edge(a, t));
		}
		
		//다익스트라 
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		//시작점 초기화
		distance[Y] = 0;
		pQ.offer(new Edge(Y, 0));
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(visited[cur.e]) continue;
			visited[cur.e] = true;
			
			for(Edge nx : graph.get(cur.e)) {
				if(!visited[nx.e] && distance[nx.e] > distance[cur.e] + nx.val) {
					distance[nx.e] = distance[cur.e] + nx.val;
					pQ.offer(new Edge(nx.e, distance[nx.e]));
				}
			}
		}

		boolean flag = false;
		Arrays.sort(distance);//최단 거리 정렬 시키고 
		//가까운ㅇ 집부터 방문한다그랬으니까
		//쟤네 중 가장 긴 거리가 X보다 크면 어차피 방문 불가 
		
		if(distance[N-1] * 2 > X) System.out.println("-1");
		
		else {
			int day = 0;
			int idx = 0;
			int tmp =0;
			
			while(idx <N ) {
				//X안으로 담을 수 있을만큼 담음 
				while(idx < N && tmp + distance[idx] * 2 <= X) {
	                tmp += distance[idx++] * 2;
	            }
	            tmp = 0;
	            day++;
			}
			System.out.println(day);
		}
	}
}

---

💚마지막 일수 누적 다른 방식

• while문이 N-1되면 바로 빠져나오기 때문에 빠져나온 상태에서 tmp의 값에 따라 일수를 누적해주는 조건문을 추가해주던가, 빠져나오는 조건 문 안에서 break직전에 tmp의 값을 처리해주면 된다.

for(int i=0; i<N; i++) {//2배 해놓고 
				distance[i] *=2;
			} 
			int cnt = 0;
		
			while(true) {
				//누적을 할 건데 
				tmp += distance[idx++];
				if(tmp > X) { //X넘어가면 
					cnt++;//카운팅해놓고 
					//직전 idx로 되돌아가기 
					idx--;
					tmp = 0;
				}
				//그러다가 N-1 넘어가면 break
				if(idx > N -1) {
					break;
				}
			}
			
			if(tmp <= X) cnt++;
			
			System.out.println(cnt);