[프로그래머스]배달

코딩테스트 연습 - 배달

문제 이해

• 양방향 그래프
• 1번 으로부터 각 지점으로의 경로 최소 비용이 k 이하인 지점들을 찾기.
• 자기 마을(1번) 도 카운트에 포함해야 한다

문제 풀이하기

하나의 지점으로부터 다른 모든 지점까지의 최소비용들을 구한다 → 최소비용이 k 이하인 지점들을 찾는다

이 경우 다익스트라(?) 를 사용해서 최소 거리 테이블을 업데이트 할 수 있다. 이 때 비용은 O(ElogV)

문제에서 N 은 50 이하, E 는 2000 이하로 주어졌기 때문에 이를 이용 할 수 있다.

• 고민되던 부분 → 리스트가 아닌 int[][] 로 graph 를 만들 경우 → a-b 사이 edge 중 최소 비용 정보만을 갖게 된다
  • 하지만 이렇게 할 경우, n^2 을 모두 돌아봐야 한다.
  • 하지만 이 경우에는, 현재까지의 최소 비용노드를 뽑아서, 해당 노드의 인접노드들을 이 노드를 거친 경우로 업데이트 하였을 때, 최소비용이 업데이트 되는 경우 → 그것이 해당 노드의 진짜 최소비용 → 다음번에는 해당 노드를 방문하지 않아도 되게 된다.
• List 로 할 경우, a-b 를 연결하는 엣지중 최소비용이 아닌 엣지로 인해, 이제까지중 최소비용이 나와도 pq에 넣어봐야 한다.
  • 최소비용이 아님에도 로직이 돌아가는 경우가 생길 것이다 (현재 상황 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static List<int[]>[] g = new List[51]; // graph

	public static int[] table = new int[51]; // 최소 비용 테이블

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;

	public static void setUp() throws IOException {

	}

	// road[i] 는 원소의 개수가 3 이다
	// 두 마을 a,b를 지나는 도로가 여러개라고 하더라도, 어차피 PQ 는 min heap 으로 만들거라.. 그 중 최소비용을 사용하게 될 거임
	public int solution(int N, int[][] road, int K) {
		int answer = 0;

		init(N, road);
		dikstra();

		answer = (int)Arrays.stream(table)
		  .filter(n -> n <= K)
		  .count();

		return answer;
	}

	public void init(int n, int[][] road) {
		for (int i = 1; i <= n; i++) {
			g[i] = new ArrayList<>();
		}

		for (int[] p : road) {
			g[p[0]].add(new int[] {p[1], p[2]});
			g[p[1]].add(new int[] {p[0], p[2]});
		}

		Arrays.fill(table, Integer.MAX_VALUE);

		table[1] = 0;

	}

	public void dikstra() {
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
		pq.add(new int[] {1, 0});

		while (!pq.isEmpty()) {
			int[] cur = pq.poll(); // 노드이름, 최소비용
			// 현재 최소비용 테이블의 비용보다 크면 패쓰
			if (table[cur[0]] < cur[1])
				continue;

			// 현재 노드의 인접노드 - adj[0] 노드 이름, adj[1] 현재노드 -> 그 노드 비용
			for (int[] adj : g[cur[0]]) {
				int nCost = cur[1] + adj[1]; // 현재 노드를 거쳐 인접노드로 갈 때 비용
				if (nCost >= table[adj[0]])
					continue;
				table[adj[0]] = nCost;
				pq.add(new int[] {adj[0], nCost});
			}
		}
	}

	public static void main(String[] args) throws IOException {
		Main main = new Main();
		int res = main.solution(5, new int[][] {{1, 2, 1}, {2, 3, 3}, {5, 2, 2}, {1, 4, 2}, {5, 3, 1}, {5, 4, 2}},
		  3);
		System.out.println(res);
		res = main.solution(6,
		  new int[][] {{1, 2, 1}, {1, 3, 2}, {2, 3, 2}, {3, 4, 3}, {3, 5, 2}, {3, 5, 3}, {5, 6, 1}},
		  4);
		System.out.println(res);
	}
}