개요
- 풀이 시간 : 40분
- 시간 제한 : 2초
- 메모리 제한 : 256MB
- 기출 : 백준 10282번 문제
- 링크 : https://www.acmicpc.net/problem/10282
문제
최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.
최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
- 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
- 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.
각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.
해결방법
컴퓨터 개수(노드)와 의존성 개수(간선)의 최대 크기가 큰 편이므로 이는 최단 경로 탐색 알고리즘 중 다익스트라를 이용해야 하는 문제라고 볼 수 있다.
문제 풀이
예제입력에 있는 2번째 케이스 경우를 생각해보자.
1단계. 일단 우선적으로 해야할 것은 1번은 2번을 가는데 2초가 걸리고, 3번으로 가는데 8초가 걸린다. 2번은 다시 3번을 4초로 갈 수 있다. 이런 정보를 저장해두어야 한다.
2단계. 그래프 정보 저장을 마쳤으면 이제 최단 거리를 탐색해야 한다. 여기서는 1번이 시작점이므로 최단 거리 테이블에 1번을 0으로 두고, 2번과 3번은 무한대로 거리를 초기화한다음 탐색을 진행한다.
3단계. 우선순위 큐(힙)에다가 (0초, 1번)을 넣는다. 그리고 나서 (0초, 1번)을 꺼내서 1번과 연관된 컴퓨터 정보 (2초, 2번), (8초, 3번)을 불러온다. 2번 저장경로는 무한대이고, 현재경로 0과 이동할 경로 2초를 더한 값과 비교해서 작은 값인 2로 업데이트 해준다. 3번도 마찬가지라서 8로 업데이트 해준다.
4단계. 힙에는 이제 (2초, 2번), (8초, 3번)이 있다. 시간이 짧은 (2초, 2번)을 꺼내서 조사를 한다. 2번과 연관된 정보는 (4초, 3번)이다. 3번 저장경로는 8초이고, 현재경로인 2초와 이동할 경로 4초를 더한값이 6초이기 때문에 1번에서 3번으로 가는것보다 2번을 거쳐서 3번으로 가는게 효과적이다. 따라서 최단 경로를 업데이트하며 힙에 추가해준다.
5단계. 힙에는 이제 (6초, 3번)과 (8초, 3번)이 있다. (6초, 3번)을 먼저 조사한다. 하지만 더이상 연관된 컴퓨터가 없으니 할게 없다. 그 다음 (8초, 3번)을 조사한다. 8초는 이미 더 나은 경로인 6초가 있기 때문에 바로 무시해버린다.
✍ 다익스트라 문제는 진짜 오랜만이다. 확인해보니 무려 한달이나 지났다... 그래서 그런지 막상 코드로 구현하려니까 못하겠더라... 그래서 다익스트라 구현 코드를 참고하면서 풀었다. 다음번에는 안보고 풀 수 있도록 하자.
✍ 3회차만에 안보고 풀었다!! 소리질러!!! (3회차는 자바스크립트로 풀었음)
Python
정답 코드
import heapq
def dijkstra(start):
q = []
# 시작 노드로 가기 우한 최단 경로는 0으로 설정하여 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있다면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접 노드들 확인
for i in computer[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
t = int(input())
for _ in range(t):
# 컴퓨터 개수 - 의존성 개수 - 시작점
n, d, c = map(int, input().split())
computer = [[] for _ in range(n + 1)]
distance = [int(1e9)] * (n + 1) # 최단거리 테이블
for _ in range(d):
# b -> a 일때만 감염. s초 걸림
a, b, s = map(int, input().split())
computer[b].append((a, s))
# 다익스트라
dijkstra(c)
count = 0
max_time = 0 # 최대 시간
for i in range(1, n + 1):
if distance[i] != int(1e9):
count += 1
if distance[i] > max_time:
max_time = distance[i]
print(count, max_time)
JavaScript
내 코드
function dijkstra(start, graph, distance) {
const queue = [];
queue.push([0, start]);
distance[start] = 0;
while (queue.length > 0) {
const [dist, now] = queue.shift();
if (dist > distance[now]) {
continue;
}
for (const node of graph[now]) {
const cost = dist + node[0];
if (cost < distance[node[1]]) {
distance[node[1]] = cost;
queue.push([cost, node[1]]);
}
}
}
return distance;
}
const t = Number(input());
for (let i = 0; i < t; i++) {
const [n, d, c] = input()
.split(' ')
.map((v) => parseInt(v));
const graph = Array.from(Array(n + 1), () => Array(0));
for (let j = 0; j < d; j++) {
const [a, b, s] = input()
.split(' ')
.map((v) => parseInt(v));
graph[b].push([s, a]);
}
const distance = Array(n + 1).fill(Infinity);
const result = dijkstra(c, graph, distance);
let count = 0;
let time = 0;
result.forEach((v) => {
if (v !== Infinity) {
count += 1;
if (time < v) {
time = v;
}
}
});
console.log(count, time);
}
자바스크립트로 힙을 구현하는건 매우 까다로운 일이다. 파이썬은 heapq 라이브러리가 있었으니까 힙을 편하게 쓸 수 있었던 거지 힙을 직접 구현하려면 .... ㄷㄷㄷ 그것도 코딩테스트 시간 촉박한데...
다익스트라에서 힙을 사용한 이유는 시간을 줄여주는 역할을 한다. 그래서 힙을 안써도 풀 수 있긴하다. 시간이 조금 염려스러웠지만 결과적으로는 성공할 수 있었다.
