[백준] 영우는 사기꾼? (C++)

[백준] 영우는 사기꾼? (C++)

백준 14676 영우는 사기꾼?

1. 문제

문제링크

2. 접근법

[ 문제 접근 ]

위상정렬을 이용해서 푸는 문제이다.

각 노드간의 관계가 중요하므로 degree 배열을 하나 선언 해 준다.

1. k 만큼 돌면서 건설을 하는지, 파괴시키는지에 따라 building 배열과 degree 배열을 활용하면 된다.

2. flag를 둬서 건설된 건물만큼 파괴되면 true, 아니면 false로 설정하고 마지막에 flag에 따라 출력시킨다.

3. 코드

#include #include #include #include using namespace std; int n, m, k; vector v[100001]; int degree[100001], building[100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int x, y, a, b; bool flag = true; cin >> n >> m >> k; for (int i = 0; i < m; i++) { cin >> x >> y; v[x].push_back(y); degree[y]++; } for (int i = 0; i < k; i++) { cin >> a >> b; //건설 if (a == 1) { //한번도 건설된 적이 없다면 if (degree[b] == 0) { building[b]++; //처음 건설된 건물이라면 if (building[b] == 1) { for (int j = 0; j < v[b].size(); j++) { degree[v[b][j]]--; } } } else { flag = false; } } else { //건설된 적이 있다면 삭제할 수 있음 if (building[b] > 0) { building[b]--; if (building[b] == 0) { for (int j = 0; j < v[b].size(); j++) { degree[v[b][j]]++; } } } else { flag = false; } } } if (flag) cout << "King-God-Emperor" << "

"; else cout << "Lier!" << "

"; return 0; }

4. 시간복잡도

이중 for문을 돌고 k는 최대 10만 * 입력받은 b의 사이즈만큼 돌린다.

5. 결과

from http://pro-grammers.tistory.com/50 by ccl(A) rewrite - 2021-09-23 18:00:20