[백준/BOJ] 백준 1412번 : 일방통행

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

1412번: 일방통행

 

사이클의 존재를 확인하는데, 양방향 도로는 단방향 도로로 만들 수 있어서 양방향 도로가 속해있는 사이클은 사이클이 존재하지 않도록 만들 수 있으므로, 단방향 도로로만 이루어진 그래프에서 사이클이 존재하는지만 확인하는 방법으로 문제를 해결했다.

 

단방향 도로로만 이루어진 그래프에서 사이클의 존재를 확인하는 방법은 플로이드 와샬을 이용해서 확인했다.

 

코드

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

int n;
int board[55][55];

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

	cin >> n;

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

		for (int j = 0; j < n; j++) {
			if (input[j] == 'Y') {
				board[i][j] = 1;
			}
			else {
				board[i][j] = 0;
			}
		}
	}

	//싸이클의 존재를 확인해야 된다
	//싸이클에 양방향 간선이 속해 있다면 해당 싸이클은 싸이클이 존재하지 않도록 만들 수 있다
	//즉 단방향 간선으로만 이루어진 싸이클이 있는지만 확인하면 된다

	//우선 단방향 간선으로만 이루어지도록 그래프를 바꾼다
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] == 1 && board[j][i] == 1) { //양방향 간선은 없앤다
				board[i][j] = 0;
				board[j][i] = 0;
			}
		}
	}

	//플로이드 와샬을 이용하여 싸이클이 존재하는지 확인한다

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				if (board[i][k] == 1 && board[k][j] == 1) {
					board[i][j] = 1;
				}

			}
		}
	}

	string result = "YES";

	for (int i = 0; i < n; i++) {
		if (board[i][i] == 1) { //자신으로 가는 길이 있을때
			result = "NO";
		}
	}

	cout << result;

	return 0;
}