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

백준 14676 : 영우는 사기꾼?

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

14676번: 영우는 사기꾼?

 

코드

//백준 14676 영우는 사기꾼?
#include <iostream>
#include <vector>

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<vector<int>> 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!" << "\n";
	}
	else if (!isLier) {
		cout << "King-God-Emperor" << "\n";
	}


	return 0;
}

설명

 

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

건물을 건설할 때

• degree(a건물을 짓기 위해 건물의 개수)가 0일 때만 건설할 수 있다. 
• 건물 한 개만 지어졌을 때 다음 건물의 degree를 감소시켜준다. (a 건물이 지어졌으므로 다음 건물이 지어질 수 있는 조건이 성립)
• degree가 0이 아닐 때는 건물을 지을 수 있는 조건이 만족하지 않으므려 isLier을 true로 값을 변경한다.

건물을 파괴할 때

• 건설한 적이 없는 건물이 파괴될 수 없으므로 isLier을 true로 값을 변경한다. 
• a건물이 지어진 건물이 한개 이상일 때 한 개를 파괴한다.
• 건물이 모두 파괴되었을 때 다음 노드를 지을 수 없기 때문에 다음 노드의 degree를 증가한다.

고찰

걸린 시간 : 1시간 반

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

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

 

난이도

Gold 4