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()!) |
'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 |