https://www.acmicpc.net/problem/16169

 

16169번: 수행 시간

첫 번째 줄에는 컴퓨터의 개수 n이 주어진다. (3 ≤ n ≤ 100) 두 번째 줄부터 n개의 줄에 걸쳐 1번부터 n번까지 각 컴퓨터의 계급과 동작 속도 t가 공백을 두고 주어진다. (1 ≤ t ≤ 100)

www.acmicpc.net

위상정렬로 접근한 문제다.

 

풀이

해당 문제의 컴퓨터는 자료를 전송할 다음 등급의 컴퓨터가 여러 대라면 동시에 자료를 전송하는 것으로 계산하면 된다. 즉 위상정렬을 통해 다음 등급의 컴퓨터를 탐색할 때, 간선의 비용이 최대 값인 경우만 찾아내면 된다.

 

입력되는 등급을 통해 위상정렬 순서를 구해 탐색을 수행한다. (다음 등급의 컴퓨터에게 자료를 전달하는 시간 + 다음 컴퓨터의 구동시간)의 최댓값을 저장할 ans 배열을 생성. 매 탐색마다 해당 배열을 최댓값으로 갱신하고 탐색이 종료된 후 ans 배열의 최댓값을 출력하면 정답이다.

 

예제를 기준으로 다음과 같이 수행된다.

가장 먼저 가장 낮은 등급의 컴퓨터인 1번과 7번 컴퓨터가 동작한다.

각자의 (동작시간 + 전송시간)의 값 중 가장 큰 값이 다음 등급인 6번 컴퓨터에게 전달되며,

해당 컴퓨터는 자신의 구동시간을 더해 ans배열에 갱신한다.

이후 탐색 큐에 6과 ans [6]의 값 36을 담아 다음 탐색을 수행한다.

2등급 컴퓨터인 6번 노드는 다음 등급의 컴퓨터인 2번과 3번 컴퓨터에 자료를 전송.

6번 컴퓨터의 대기시간 + 동작시간의 값 + 전송시간의 값이 전달된다.

이제 해당 값에 2번과 3번 컴퓨터의 구동시간을 더해 ans배열을 갱신한다.

각 노드로 진입하는 대기시간 + 구동시간 + 전송시간의 값 중 가장 큰 값을 입력받아 ans배열을 갱신해 나가면 된다.

구동시간에는 음수가 입력되지 않으므로 마지막 컴퓨터의 대기시간 + 구동시간 + 동작시간을 더해 출력하면 된다.

 

정답 코드

import Foundation
let N = Int(readLine()!)!
var grade = Array(repeating: [Int](), count: N)
var arr = Array(repeating: [Int](), count: N)
var operTime = Array(repeating: Int(), count: N)
var indegree = Array(repeating: 0, count: N)
var ans = Array(repeating: 0, count: N)
for i in 0..<N{
let line = readLine()!.split(separator: " ").map{Int($0)!}
let g = line[0]-1
grade[g].append(i)
operTime[i] = line[1]
}
for i in 0..<N-1{
let curr = grade[i]
let next = grade[i+1]
for k in 0..<curr.count{
let U = curr[k]
for p in 0..<next.count{
let V = next[p]
arr[U].append(V)
indegree[V] += 1
}
}
}
var q = [(num:Int, time:Int)]()
for i in 0..<N{
if indegree[i] == 0{
q.append((i,operTime[i]))
ans[i] = operTime[i]
}
}
var idx = 0
while idx < q.count{
let currNum = q[idx].num
let currTime = q[idx].time
for next in arr[currNum]{
let transTime = (currNum-next)*(currNum-next)+currTime
ans[next] = max(ans[next], transTime+operTime[next])
indegree[next] -= 1
if indegree[next] == 0{
q.append((next,ans[next]))
}
}
idx += 1
}
print(ans.max()!)
view raw 16169.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[5719] 거의 최단 경로  (0) 2023.04.30
[1711] 직각삼각형  (0) 2023.04.19
[24526] 전화 돌리기  (0) 2023.04.05
[14907] 프로젝트 스케줄링  (0) 2023.04.03
[2637] 장난감 조립  (0) 2023.04.01

+ Recent posts