PS/BaekJoon
[1005] ACM Craft - 위상정렬 ★★☆☆ / 복습 ○
JIK_
2021. 11. 20. 23:35
[ 문제 ] : https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
[ 문제 접근 ]
- 기본적인 위상 정렬 문제지만, time 배열을 만들고 값을 업데이트 해나가야 하는 문제.
[ 처음 풀이 ]
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using std::cout; using std::cin;
using std::vector;
int N, K, W;
vector<std::pair<int,int>> graph[1001];
int time[1001];
int indegree[1001];
/* # 위상 정렬 풀이 #
1. 그래프를 입력을 받으면서 indegree 배열을 같이 갱신해준다.
2. queue 에 indegree == 0 인 노드를 전부 집어놓고
3. queue 에 노드를 꺼내서 꺼낸 노드의 인접한 노드들의 indegree 전부 1씩 줄여준다.
4. 인접한 노드의 줄어든 indegree 가 0이라면 queue 에 넣고 반복한다.
*/
void solve(int W) {
// 2. queue 에 indegree == 0 인 노드를 전부 집어놓고
std::queue<std::pair<int,int>> que;
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
que.push({ i,time[i] });
}
}
while (!que.empty()) {
int cur = que.front().first;
// 현재 총 시간 += 처음 건물 짓는 시간
int cur_time = que.front().second;
if (cur == W) { // 목적지 도착.
cout << time[cur] << '\n';
return;
}
que.pop();
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur][i].first;
int next_time = cur_time +graph[cur][i].second;
// 현재 time[next] 보다 클 경우 갱신.
if (next_time > time[next]) {
time[next] = next_time;
}
// 3. queue 에 노드를 꺼내서 꺼낸 노드의 인접한 노드들의 indegree 전부 1씩 줄여준다.
indegree[next]--;
// 4. 인접한 노드의 줄어든 indegree 가 0이라면 queue 에 넣고 반복한다.
if (indegree[next] == 0) {
que.push({ next,time[next] });
}
}
}
}
void initiate() {
for (int i = 1; i <= N; i++) {
graph[i].clear();
}
std::fill_n(time+1,N,0);
std::fill_n(indegree+1,N,0);
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> time[i];
}
while (K--) {
int a, b;
cin >> a >> b;
graph[a].push_back({ b,time[b] });
// 1. 그래프를 입력을 받으면서 indegree 배열을 같이 갱신해준다.
indegree[b]++;
}
cin >> W;
solve(W);
initiate();
}
return 0;
}
풀고 보니, 그래프 입력 받을때 굳이 pair로 안받아줘도 될거 같다라는 생각에 공간 복잡도를 줄이는 방향으로 다시 풀어봤다.
[ 개선된 풀이 ]
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using std::cout; using std::cin;
using std::vector;
int N, K, W;
vector<int> graph[1001];
int time[1001];
int result_time[1001];
int indegree[1001];
void solve(int W) {
std::queue<int> que;
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
que.push(i);
result_time[i] = time[i];
}
}
while (!que.empty()) {
int cur = que.front();
if (cur == W) { // 목적지 도착.
cout << result_time[cur] << '\n';
return;
}
que.pop();
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur][i];
if (result_time[next] < result_time[cur]+ time[next]) {
result_time[next] = result_time[cur] + time[next];
}
indegree[next]--;
if (indegree[next] == 0) {
que.push(next);
}
}
}
}
void initiate() {
for (int i = 1; i <= N; i++) {
graph[i].clear();
}
std::fill_n(time+1,N,0);
std::fill_n(result_time+1, N, 0); // +1 안해주면 틀린다... 고생 좀 했다..
std::fill_n(indegree+1,N,0);
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> time[i];
}
while (K--) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
indegree[b]++;
}
cin >> W;
solve(W);
initiate();
}
return 0;
}
[ Key Point ]
👉 문제에서 test case 횟수가 주어졌을땐 반드시 전역 변수 값을 초기화하자!
void initiate() {
for (int i = 1; i <= N; i++) {
graph[i].clear();
}
std::fill_n(time+1,N,0);
std::fill_n(result_time+1, N, 0); // +1 안해주면 틀린다... 고생 좀 했다..
std::fill_n(indegree+1,N,0);
}
[ 다른 사람 풀이 ]