[백준/BOJ] 백준 1432번 : 그래프 수정

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

1432번: 그래프 수정

 

플로이드 와샬을 통해 그래프의 사이클이 존재하는지 확인하였고, 위상 정렬을 이용해서 정점의 번호를 매기는 방법을 통해 문제를 해결했다.

 

이때 주의해야 될 점은, 그래프 간선의 방향을 거꾸로 하여 위상 정렬을 수행하면서 우선순위 큐에서 정점의 번호가 큰 것부터 나오게 하여 정점의 번호가 큰 정점부터 새로운 큰 번호를 부여해 나아가는 방식으로 문제를 해결해야 한다. 왜냐하면 그래프의 방향을 거꾸로 하지 않고 위상정렬을 수행할 때 우선순위 큐에서 정점의 번호가 작은 것부터 나오게 하여 정점의 번호가 작은 정점부터 새로운 작은 번호를 부여해 나아간다면 반례가 발생하기 때문이다 (반례 예시 : N=5, 4->1, 1->5, 3->2, 2->5 인 그래프)

 

코드

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

int n;
vector<int> result(55, 0);
vector<vector<int>> board(55, vector<int>(55, 0));
vector<int> re_adj[55];
vector<int> re_indegree(55, 0);
priority_queue<int> pq;
int id_cnt;

//플로이드 와샬 방법으로 싸이클이 존재하는지 확인
bool CheckCycle() {

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (board[i][k] == 1 && board[k][j] == 1) {
					board[i][j] = 1;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (board[i][i] == 1) {
			return true;
		}
	}

	return false;
}

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

	cin >> n;

	for (int i = 1; i <= n; i++) {
		string input;
		cin >> input;

		for (int j = 1; j <= n; j++) {
			if (input[j - 1] == '1') {
				board[i][j] = 1;

				//그래프의 방향을 거꾸로 하여, 거꾸로 번호를 매기는 방법으로 문제를 해결한다
				//그래프의 방향을 뒤집지 않고 그대로 하면, 사전순으로 제일 앞서는것 출력 하는 부분에서 반례가 발생
				//반례 ex N=5, 4->1, 1->5, 3->2, 2->5
				re_adj[j].push_back(i);
				re_indegree[i]++;
			}
			else {
				board[i][j] = 0;
			}
		}
	}

	//싸이클이 존재하는지 우선 확인한다
	if (CheckCycle()) {
		cout << -1;
		return 0;
	}

	for (int i = 1; i <= n; i++) {
		if (re_indegree[i] == 0) {
			pq.push(i);
		}
	}

	id_cnt = n;
	while (!pq.empty()) {
		int here = pq.top(); //현재 우선순위 큐에 있는 정점 중 가장 번호가 큰 것 부터 큰 번호를 부여한다
		pq.pop();

		result[here] = id_cnt;
		id_cnt--;

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

			re_indegree[there]--;

			if (re_indegree[there] == 0) {
				pq.push(there);
			}
		}
	}


	for (int i = 1; i <= n; i++) {
		cout << result[i] << " ";
	}

	return 0;
}