250x250
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 막내의막무가내 프로그래밍
- 부스트코스에이스
- 안드로이드 Sunflower 스터디
- 막내의막무가내 목표 및 회고
- 막내의막무가내 플러터 flutter
- flutter network call
- 안드로이드 sunflower
- 막내의막무가내 SQL
- 막내의막무가내 알고리즘
- 막내의막무가내
- 막내의 막무가내
- 주엽역 생활맥주
- 2022년 6월 일상
- 안드로이드
- 막내의막무가내 안드로이드
- 막내의 막무가내 알고리즘
- 막무가내
- 막내의막무가내 안드로이드 에러 해결
- 프로그래머스 알고리즘
- 막내의막무가내 코볼 COBOL
- 막내의막무가내 일상
- 막내의막무가내 안드로이드 코틀린
- 막내의막무가내 rxjava
- 막내의막무가내 플러터
- 프래그먼트
- 주택가 잠실새내
- Fragment
- 막내의막무가내 코틀린
- 부스트코스
- 막내의막무가내 코틀린 안드로이드
Archives
- Today
- Total
막내의 막무가내 프로그래밍 & 일상
[알고리즘] 백준 10282 해킹 -다익스트라- 자바 본문
728x90
백준 다익스트라 유형의 10282번 해킹 문제를 풀어봤습니다. ㅎㅎ
다익스트라의 기본 유형 문제였습니다.
풀이는 다음과 같습니다.
[Java]
import java.util.*;
public class Main {
private static int T; //테스트 케이스 수
private static int N; //컴퓨터 개수
private static int D; //의존성 개수
private static int C; //해킹당한 컴퓨터 번호
private static int[] distances; // 최단거리
private static List<Edge>[] edgeList;
private static int cnt = 0; // 총 감염되는 컴퓨터 수
private static int time = 0; // 마지막 컴퓨터가 감염되기까지의 걸리는 시간
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for (int t = 0; t < T; t++) {
N = sc.nextInt();
D = sc.nextInt();
C = sc.nextInt();
distances = new int[N + 1];
edgeList = new ArrayList[N + 1];
Arrays.fill(distances, Integer.MAX_VALUE);
for (int i = 0; i <= N; i++) {
edgeList[i] = new ArrayList<>();
}
for (int i = 0; i < D; i++) {
int a = sc.nextInt(); //컴퓨터 a
int b = sc.nextInt(); //컴퓨터 b
int s = sc.nextInt(); //S초 후 감염
edgeList[b].add(new Edge(a, s)); // 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다. (a, b 거꾸로 주의)
}
distances[C] = 0;
dijkstra();
cnt = 0;
time = 0;
for (int i = 1; i <= N; i++) {
if (distances[i] != Integer.MAX_VALUE) {
cnt++;
time = Math.max(time, distances[i]);
}
}
System.out.println(cnt + " " + time);
}
}
private static void dijkstra() {
PriorityQueue<Edge> queue = new PriorityQueue<>();
queue.add(new Edge(C, 0));
while (!queue.isEmpty()) {
Edge edge = queue.poll();
int vertex = edge.vertex;
int cost = edge.cost;
if (distances[vertex] < cost) {
continue;
}
for (int i = 0; i < edgeList[vertex].size(); i++) {
int vertex2 = edgeList[vertex].get(i).vertex;
int cost2 = edgeList[vertex].get(i).cost + cost;
if (distances[vertex2] > cost2) {
distances[vertex2] = cost2;
queue.add(new Edge(vertex2, cost2));
}
}
}
}
private static class Edge implements Comparable<Edge> {
int vertex;
int cost;
public Edge(int vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return cost - o.cost;
}
}
}
댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!
728x90
'알고리즘 > 다익스트라' 카테고리의 다른 글
[알고리즘] 백준 4485 녹색 옷 입은 애가 젤다지? -다익스트라 + BFS, 최단경로 - 자바 코틀린 (0) | 2021.04.12 |
---|---|
[알고리즘] 백준 18352 특정 거리의 도시 찾기 -최단경로, 다익스트라- 자바 (0) | 2021.04.11 |
[알고리즘] 프로그래머스 배달 -최단경로, 다익스트라- 자바Summer/Winter Coding(~2018) (0) | 2021.03.24 |
[알고리즘] 백준 11779 최소비용 구하기 2 -다익스트라, 최단경로- (2) | 2020.12.27 |
[알고리즘] 백준 1504 특정한 최단 경로 -최단경로, 다익스트라- 자바 (0) | 2020.11.27 |