[プログラマ]配信
25149 ワード
コーディングテストの練習-配信
双方向図 1号から各場所へのルートは、kより最小コストの低い場所を探しています. 自分の村(1号)もカウントに含めるべき
一つの場所から他のすべての場所への最低料金→最低料金k以下の場所を探す
この場合すべてExtra(?)最小距離テーブルの更新を使用できます.この場合のコストはO(EGV)
問題はNが50以下、Eが2000以下なので使用可能です.で悩んでいる部分→リストではなくint[]]を使用して図を作成すると、→a-b間のエッジに最小料金情報のみが含まれます でもそうすればn^2は振り返ります. ただし、この場合、これまでの最小費用ノードを選択し、そのノードの隣接ノードをそのノードを経由するように更新した場合、更新の最小費用→そのノードの真の最小費用→次回はそのノードにアクセスする必要はありません. Listであれば、a-bを接続するEdgeでは最小料金ではなく、これまで最小料金であったとしてもpqに入れる. の最低コストでなくても、論理ループ(現在の状況) が発生する.
問題を理解する
問題を解く
一つの場所から他のすべての場所への最低料金→最低料金k以下の場所を探す
この場合すべてExtra(?)最小距離テーブルの更新を使用できます.この場合のコストはO(EGV)
問題はNが50以下、Eが2000以下なので使用可能です.
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);
}
}
Reference
この問題について([プログラマ]配信), 我々は、より多くの情報をここで見つけました https://velog.io/@ynoolee/프로그래머스배달テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol