서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다. 따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다. 프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.
[입력] 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, ..., DN이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.
[출력] 건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다. 건설순서는 모든 건물이 건설 가능하도록 주어진다.
문제를 요약하자면..
1번부터 N번까지의 N개의 건물이 있을 때, 주어진 건설 순서 (1 2 = 1->2) 에 따라서 각 건물이 건설될 수 있다.
예를 들어 앞의 그림에 따르면, 2와 3은 1이 건설된 후에야 건설할수 있고, 4는 2와 3이 모두 건설된 후에야 건설할 수 있다.
각 건물을 건설하는데에는 DN의 시간이 소요되고, 입력으로 주어진다.
이때 입력으로 받는 건물 W를 건설하는데 소요되는 최소시간을 구하는 문제이다.
✅ 문제 풀이
W를 건설하기 위해서는 W하위에 연결된 모든 건물이 완료되어야 하기 때문에, W까지 연결되는 여러 경로 중 에서 소요되는 시간이 최대일 때와 같다.
=> 왜 최대이냐?
W가 건설되기 전까지는, W를 건설하기 위해 먼저 건설되어야 하는 건물들 모두가 건설을 마쳐야 W를 건설할 수 있기 때문에, 위의 예시처럼 건물 2가 1초 밖에 걸리지 않다 하더라도, 건물4가 건설되려면 건물3도 건설되어야 하므로, 둘 중 더 소요시간이 긴 건물 3에 의해 100초가 더해져야 한다. 따라서 총 10초(건물1)+100초(건물2,3)+10초(건물4)=120초가 소요된다.
따라서 이 문제는 위상정렬을 이용해서 해결할 수 있다.
다음 사항들을 고려해야 한다.
1. 각 건물(노드)을 건설한 바로 다음에 건설될 수 있는 건물들을 저장해야 한다. => vector<int> node[1005]를 vector 타입의 배열을 만들어서, 각 노드(인덱스=건물번호)에 이전 건물에 대한 정보를 vector로 추가해준다.
2. 각 건물까지 짓는데 걸리는 최소 시간을 저장하는 배열이 있어야 한다.
=> vector<int> sum(1005,0); => 각 노드(인덱스=건물번호)에 저장한다.
3. 각 건물에 대한 깊이를 저장하는 배열이 있어야 한다. => 예시에서 보면 1은 선행 노드가 없으므로 깊이가 0, 2와 3은 선행노드가 1이 있으므로 1, 4는 선행노드가 1, 2-3이 있으므로 2이다.
=> vector<int> degree(1005,0)
이제 코드를 하나씩 만들어가 보자.
테스트 케이스 T를 받아 저장한다.
T번의 테스트 케이스를 진행하도록 for문을 작성하고, for문 안에서 아래 내용들이 동작하도록 구현한다.
건물을 개수를 입력받아 N에 저장한다.
건설 규칙의 개수를 입력받아 K에 저장한다.
다음을 미리 선언해준다. ✔ vector<int> D(1005,0) : 각 건물의 건설시간을 담은 크기가 1005인 벡터 D ✔ vector<int> sum(1005,0) : 각 건물을 완성하기까지 걸리는 시간을 담은 크기가 1005인 벡터 sum ✔ vector<int> node[1005] : 각 건물의 후행 건물을 담은 벡터 타입의 크기가 1005인 배열 node ✔ vector<int> degree(1005,0) : 각 건물(노드)의 깊이를 담은 크기가 1005인 벡터 degree =>값은 모두 0으로 초기화
각 건물의 건설시간을 건물 번호에 맞게 차례로 입력받는다. => 벡터 D의 1번 인덱스부터 1번 건물의 건설 시간을 입력받아 저장한다. => 그리고 sum의 동일한 인덱스에 입력받은 각각의 건설 시간을 저장해준다. sum에는 일단 각 건물에 대한 건설시간이 저장되어 있는 것이다. = 만약 맨 아래 노드라면 해당 건물을 짓는데는 해당 건물의 건설시간만 소요될 것이므로 미리 값을 지정해준다.
K개의 건설 규칙을 입력받자. for문을 연다.
건설 규칙을 입력받기 위해 선행 건물을 저장하는 x와, 후행 건물을 저장하는 y를 선언하고, 입력받아 저장한다.
node[x]에다가 y를 넣어준다. 현재 이 배열은 벡터 타입이므로 push_back하여 y를 저장한다.
그리고 y 이전에 x가 먼저 건설되기 때문에, y는 선행 노드가 있다는 것이므로, degree[y]를 1 늘려줘서 깊이를 1 높인다.
이렇게 K개의 규칙에 대해 다 실행한 후 for문이 끝나면 경로를 하나씩 접근해가며 sum을 갱신할 수 있다.
그 전에 W를 입력받아서 저장해둔다.모든 건물의 sum을 구한 후 그중 sum[W]를 통해 W건물까지 짓는데 걸리는 최소시간을 구할 수 있다. 다음을 진행하여 sum을 설정하자.
queue<int> q를 하나 생성하여 방문할 노드들을 저장하는 용도로 사용하자.
일단 모든 건물(=노드)를 for문을 통해 돌아보면서, 현재 노드의 degree가 0인지 확인한다.
현재 노드의 degree가 0이라면, 선행 노드가 없다는 것이므로, q에 현재 노드를 push한다.
for문을 다 돌면, while문을 통해 q가 빌 때 까지 다음을 수행한다.
q의 맨 앞에 있는 노드를 꺼내 top에 저장한다. 그리고 node[top]에 저장된 모든 후행 노드를 순회하면서 next에 저장한다.
만약 sum[top]+D[next] 가 sum[next]보다 크다면 sum[next]를 전자로 갱신시켜준다. =>이게 바로 같은 레벨에서는 최대로 걸리는 값으로 갱신해야 한다는 의미이다. 같은 레벨에 있는 건물은 다음 건물 짓기 전에 모두 건설완료되어야 하기 때문에 가장 오래 걸리는 건설 시간을 반영한다는 뜻이다.
그리고 degree[next]를 1 줄여서 선행 노드를 이미 방문했음을 표시한다.
그리고 degree[next]가 0이면 이 노드를 시작으로 위 과정을 반복하기 위해 q에 push한다.
그럼 while문을 충족하므로 과정을 반복한다.
맨 마지막 노드에서 degree[next]를 1 줄임으로써 0이 되면서 while문이 종료되고, 각 노드에 대한 최종 sum이 설정되었을 것이다.
그럼 이때 sum[W]를 출력하여 프로그램을 마친다.
☑ 코드 전문
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int N, K, W, top, next;
vector<int> D(1005, 0);//각 건물의 건설시간
vector<int> node[1005];//노드 별 이어지는 노드
vector<int> degree(1005, 0);//루트로부터 몇번째에 있는지
vector<int> sum(1005, 0);//현재 노드까지의 총 건설 시간
queue<int> q;
cin >> N >> K;
for (int j = 1; j <= N; j++) {
cin >> D[j];
sum[j] = D[j];
}
for (int j = 0; j < K; j++) {
int x, y;
cin >> x >> y;
node[x].push_back(y);
degree[y]++;
}
cin >> W;
for (int j = 1; j <= N; j++) {
if (!degree[j]) {//내 아래로 없으면
q.push(j);//이 노드의 후행 노드들을 살펴보자
}
}
while (!q.empty()) {
top = q.front();
q.pop();
for (int j = 0; j < node[top].size(); j++) {
next = node[top][j];
if (sum[top] + D[next] > sum[next]) sum[next] = sum[top] + D[next];
degree[next]--;
if (!degree[next]) q.push(next);
}
}
cout << sum[W]<<"\n";
}
return 0;
}
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
✅ 문제풀이
간단하게 queue를 이용
queue에 1부터 N까지 값을 차례로 넣은 후, 앞에서부터 K-1번 빼서 뒤로 다시 넣는다.
그럼 K번째 값이 queue의 맨 앞에 위치하게 되고, 해당 값을 answer에 넣어주고, queue에서 삭제한다.
위 과정을 queue의 크기가 1이 될때까지 반복한다.
queue에 하나의 값만 남게 되면, 그 값을 answer에 넣어준다.
그리고 출력 형식에 맞게, answer에 있는 값을 차례로 출력해주면 된다.
아래 그림처럼 동작하게 된다. (예제로 예를 들어보자)
1. queue에 1부터 7까지 넣은 모습이다.
2. 3번 째 값을 제거하기 위해서 앞에서부터 뒤로 넘겨주어야 한다.
1번 째 값을 queue에서 pop하고, 다시 동일한 queue에 push하여 뒤로 넘어가게 한다.
3. 2번 째 값을 queue에서 pop하고, 다시 동일한 queue에 push하여 뒤로 넘어가게 한다.
4. 드디어 3(=K)번 째 값에 도달했으니, 이 값은 answer에 넣어주고, queue에서 삭제해준다.
5. 위의 과정을 아래 queue의 길이가 1이 될 때까지(=마지막 하나만 남을때까지) 반복해주면 된다.
최종 코드는 아래와 같다.
#include<iostream>
#include<queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
cin >> N >> K;
queue<int> q;
queue<int> answer;
for (int i = 1; i <= N; i++) {
q.push(i);
}
while (q.size() > 1) {
for (int i = 1; i < K; i++) {
int temp = q.front();
q.pop();
q.push(temp);
}
answer.push(q.front());//k번 째 빼기
q.pop();
}
answer.push(q.front());
q.pop();
cout << "<"<<answer.front();
answer.pop();
while (!answer.empty()) {
cout << ", " << answer.front();
answer.pop();
}
cout << ">";
}
