BOJ(C++) / 백준 14676 : 영우는 사기꾼?

BOJ(C++) / 백준 14676 : 영우는 사기꾼?

728x90

백준 14676 : 영우는 사기꾼?

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

코드

//백준 14676 영우는 사기꾼? #include #include using namespace std; int degree[100001] = { 0, }; int build[100001] = { 0, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m, k; cin >> n >> m >> k; vector> graph(n + 1); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; graph[x].push_back(y); degree[y]++; // 이전 노드 개수 } int isLier = false; for (int i = 0; i < k; i++) { int oper, a; cin >> oper >> a; if (isLier) { continue; } if (oper == 1) { // 이전 노드가 없거나, 다 지어졌을 때 if (degree[a] == 0) { build[a]++; // 처음 건설되었을 때 if (build[a] == 1) { for (int j = 0; j < graph[a].size(); j++) { degree[graph[a][j]]--; } } } else { isLier = true; continue; } } else if (oper == 2) { // 건설한적 없는 건물이 파괴될 때 if (build[a] == 0) { isLier = true; continue; } else { build[a]--; // 건물이 모두 파괴되었을 때 if (build[a] == 0) { for (int j = 0; j < graph[a].size(); j++) { degree[graph[a][j]]++; } } } } } if (isLier) { cout << "Lier!" << "

"; } else if (!isLier) { cout << "King-God-Emperor" << "

"; } return 0; }

설명

graph에 건물 관계를 저장해준다. 또한 해당 건물을 짓기 위해서 필요한 건물들의 개수를 degree에 저장해준다.

건물을 건설할 때

degree(a건물을 짓기 위해 건물의 개수)가 0일 때만 건설할 수 있다.

건물 한 개만 지어졌을 때 다음 건물의 degree를 감소시켜준다. (a 건물이 지어졌으므로 다음 건물이 지어질 수 있는 조건이 성립)

degree가 0이 아닐 때는 건물을 지을 수 있는 조건이 만족하지 않으므려 isLier을 true로 값을 변경한다.

건물을 파괴할 때

건설한 적이 없는 건물이 파괴될 수 없으므로 isLier을 true로 값을 변경한다.

a건물이 지어진 건물이 한개 이상일 때 한 개를 파괴한다.

건물이 모두 파괴되었을 때 다음 노드를 지을 수 없기 때문에 다음 노드의 degree를 증가한다.

고찰

걸린 시간 : 1시간 반

조건들을 잘 확인하지 않고 풀어서 틀리고, 시간초과로 틀리고 계속해서 틀렸었다. 결국 구글링으로 문제를 풀 수 있었고 부족함을 많이 느꼈다. 위상정렬 문제이다. 보통 위상정렬 문제는 queue를 사용하여 풀 수 있지만, 다음과 같이 푸는 방법도 있다는 것을 알게 되었다.

오랜만에 문제를 풀어서 그런지 문제가 쉽게 풀리지 않았다. 문제풀이는 진짜 꾸준히 해야겠다.

난이도

Gold 4

728x90

from http://se-jung-h.tistory.com/206 by ccl(A) rewrite - 2021-12-21 18:00:06