[プログラマ]配信

25149 ワード

コーディングテストの練習-配信

問題を理解する

  • 双方向図
  • 1号から各場所へのルートは、kより最小コストの低い場所を探しています.
  • 自分の村(1号)もカウントに含めるべき
  • 問題を解く


    一つの場所から他のすべての場所への最低料金→最低料金k以下の場所を探す
    この場合すべてExtra(?)最小距離テーブルの更新を使用できます.この場合のコストはO(EGV)
    問題はNが50以下、Eが2000以下なので使用可能です.
  • で悩んでいる部分→リストではなくint[]]を使用して図を作成すると、→a-b間のエッジに最小料金情報のみが含まれます
  • でもそうすればn^2は振り返ります.
  • ただし、この場合、これまでの最小費用ノードを選択し、そのノードの隣接ノードをそのノードを経由するように更新した場合、更新の最小費用→そのノードの真の最小費用→次回はそのノードにアクセスする必要はありません.
  • Listであれば、a-bを接続するEdgeでは最小料金ではなく、これまで最小料金であったとしても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);
    	}
    }