[백준/BOJ] 백준 13147번 : Dwarves

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

13147번: Dwarves

 

작은 쪽에서 큰 쪽으로 이동하는 그래프를 만들어, 해당 그래프에서 위상 정렬을 통해 모든 정점을 방문할 수 있으면 가능한 경우이고, 그렇지 않으면 불가능한 경우로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

int n;
unordered_map<string, int> name_id;
int name_id_cnt = 0;

vector<int> adj[100005];
int indegree[100005];

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		string s1, r, s2;
		cin >> s1 >> r >> s2;

		if (name_id.count(s1) == 0) {
			name_id_cnt++;
			name_id.insert(make_pair(s1, name_id_cnt));
		}
		if (name_id.count(s2) == 0) {
			name_id_cnt++;
			name_id.insert(make_pair(s2, name_id_cnt));
		}

		int s1_id = name_id[s1];
		int s2_id = name_id[s2];

		if (r == "<") {
			adj[s1_id].push_back(s2_id);
			indegree[s2_id]++;
		}

		else {
			adj[s2_id].push_back(s1_id);
			indegree[s1_id]++;
		}
	}

	int visited_cnt = 0;

	queue<int> q;
	for (int i = 1; i <= name_id_cnt; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		visited_cnt++;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];

			indegree[there]--;

			if (indegree[there] == 0) {
				q.push(there);
			}
		}
	}

	if (visited_cnt == name_id_cnt) {
		cout << "possible";
	}
	else {
		cout << "impossible";
	}

	return 0;
}