[알고리즘]프로그래머스 12978번 - 배달

프로그래머스 12978번 - 배달

프로그래머스 12978번 - https://programmers.co.kr/learn/courses/30/lessons/12978

 

요구사항

1. N개의 마을 중 K 시간 이하로 배달이 가능한 마을의 개수를 반환하라.

2. 서로 다른 마을 간에 이동할 때는 도로를 지나야 합니다.

3. 도로를 지날 때 걸리는 시간은 도로별로 다르며, 두 마을을 연결하는 도로는 여러 개가 있을 수 있습니다.

 

요구사항 분석 및  풀이과정

1. 전형적인 최단경로 알고리즘 문제입니다.

2. 주어진 도로 정보들로 그래프를 구축하여 최단경로 알고리즘 중 편한 알고리즘을 사용하면 됩니다.

3. 저는 다익스트라 알고리즘을 사용하도록 하겠습니다.

4. 1번 마을에서 각 마을(1번 마을 포함)까지의 최단 배달 시간을 구한 후, K 이하인 마을의 개수를 세어줍니다.

 

소스코드 작성

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

class Solution {

	private static class Dijkstra {

		public static final int INF = 987654321;

		public static class Pair implements Comparable<Pair> {

			private final int x;
			private final int y;

			public Pair(int x, int y) {
				this.x = x;
				this.y = y;
			}

			public int getX() {
				return x;
			}

			public int getY() {
				return y;
			}

			@Override
			public int compareTo(Pair o) {
				if (this.x == o.x) {
					return this.y - o.y;
				}

				return this.x - o.x;
			}
		}

		private Dijkstra() {
		}

		/*
		 * Queue`s Element Pair = (cost, vertex)
		 * Graph`s Element Pair = (dest, cost)
		 * n : number of vertices ( n >= 1 )
		 * start : start vertex number ( start >= 1 )
		 * return : shortest cost
		 * result[i] = shortest cost for start to i ( 1 <= i <= n )
		 * if result[i] is INF, can't approach at i
		 * */
		public static int[] dijkstra(int n, int start, List<List<Pair>> graph) {
			int[] cost = new int[n];
			Arrays.fill(cost, INF);

			PriorityQueue<Pair> q = new PriorityQueue<>();
			q.offer(new Pair(0, start));
			cost[start] = 0;

			while (!q.isEmpty()) {
				Pair cur = q.poll();
				int nowCost = cur.getX();
				int nowVertex = cur.getY();

				if (cost[nowVertex] != nowCost) {
					continue;
				}

				for (Pair next : graph.get(nowVertex)) {
					int nextVertex = next.getX();
					int nextCost = nowCost + next.getY();

					if (nextCost < cost[nextVertex]) {
						cost[nextVertex] = nextCost;
						q.offer(new Pair(nextCost, nextVertex));
					}
				}
			}

			return cost;
		}
	}

	public int solution(int N, int[][] roads, int K) {
		List<List<Dijkstra.Pair>> graph = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<>());
		}

		for (int[] road : roads) {
			int from = road[0] - 1;
			int to = road[1] - 1;
			int cost = road[2];

			graph.get(from).add(new Dijkstra.Pair(to, cost));
			graph.get(to).add(new Dijkstra.Pair(from, cost));
		}

		int[] distance = Dijkstra.dijkstra(N, 0, graph);
		int result = 0;

		for (int i = 0; i < N; i++) {
			if (distance[i] <= K) {
				result++;
			}
		}

		return result;
	}
}

 

결과

 

소스코드 깃허브 주소

링크