[백준/BOJ] 백준 14676번 : 영우는 사기꾼?

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

14676번: 영우는 사기꾼?

 

건물 간의 관계를 그래프로 표현하고, indegree도 저장하여, 건물이 건설되면 해당 건물의 영향을 받아 건설이 될 수 있는 건물의 indegree를 줄이고, 건물이 파괴되면 해당 건물의 영향을 받아 건설이 될 수 있는 건물들의 indegree를 늘려서 정상적으로 건물을 건설하거나 파괴할 수 있는지 판단했다.

 

이때, 건물들은 중복 건설이 가능하므로 building_cnt[해당 건물]에 해당 건물의 개수를 저장해서 짓든 건물이 이전에는 지어지지 않았던 건물을 짓는 상황인지 또는 파괴하는 건물을 파괴하면 남는 건물이 없는 상황인지를 파악해서 해당 건물로 인해 영향을 받아 건설이 될 수 있는 건물에 실질적으로 영향을 주는지를 확인해서 문제를 해결했다. 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, k;
vector<int> adj[100005];
vector<int> building_cnt(100005, 0); //빌딩의 개수
vector<int> indegree(100005, 0);

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;

		adj[x].push_back(y);
		indegree[y]++;
	}

	bool result = true;
	for (int i = 0; i < k; i++) {
		int command, a;
		cin >> command >> a;

		if (command == 1) { //건설일때, 즉 건설할 수 없는 건물인지 확인

			if (indegree[a] != 0) { //건설할 수 없는 건물일때
				result = false;
				break;
			}

			else { //건설할 수 있는 건물일때

				building_cnt[a]++; //빌딩 개수 추가

				if (building_cnt[a] == 1) { //이전에는 지어져있지 않던 건물일때

					//영향을 주는 건물들 indegree 줄이기
					for (int j = 0; j < adj[a].size(); j++) {
						int there = adj[a][j];
						indegree[there]--;
					}

				}

			}
		}

		else { //파괴일때, 즉 없는 건물을 파괴하는지 확인

			if (building_cnt[a] == 0) { //건물이 없을때
				result = false;
				break;
			}

			else { //건물을 파괴할 수 있을때

				building_cnt[a]--;

				if (building_cnt[a] == 0) { //남는 건물이 없어졌을때

					//영향을 주는 건물들 indegree 늘리기
					for (int j = 0; j < adj[a].size(); j++) {
						int there = adj[a][j];
						indegree[there]++;
					}

				}

			}

		}
	}

	if (result == true) {
		cout << "King-God-Emperor";
	}

	else {
		cout << "Lier!";
	}

	return 0;
}