백준1613 - 역사

 

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

1613번: 역사

플로이드 와샬 알고리즘을 이용하였다.

사건의 연관관계가 있으면 1을 넣어주고 그렇지 않으면 INF를 넣었다.

결론적으로 사건의 연관관계가 있다면 INF값이 들어가지 않고 플로이드 와샬 알고리즘을 적용할 결과(최소비용)가 들어간다.

 

ex.1) d[1][4] = 5

1 -> 4로 가는데 총 4번에 사건이 있다. 1은 4보다 앞선다.

 

ex.2) d[6][4] = 2

6 -> 4로 가는데 총 2번에 사건이 있다. 6은 4보다 앞선다.

 

ex.3) d[1][6] = 3

1 -> 6으로 가는데 총 3번에 사건이 있따. 1은 6보다 앞선다. 

//시간초과가 나서 scanf를 사용하였다.
#include <iostream>
#include <vector>
#define INF 1000000
using namespace std;

int n; //사건의 갯수
int k; //사건 전후 관계의 개수
int s; //원하는 사건의 전후를 알고 싶은 경우
int mat[401][401]; //사건의 경위를 입력할 변수
int d[401][401]; //플로이드 와샬 결과를 입력할 변수

//처음 배열을 세팅, 401 X 401칸
void setting() {
	for (int i = 0; i <= 400; i++) {
		for (int j = 0; j <= 400; j++) {
			if (i == j) {
				mat[i][j] = 0; //자기 자신은 0으로 초기화
			}
			else {
				mat[i][j] = INF; //자기 자신 외에 다른 공간은 INF로 초기화
			}
		}
	}
}

void FloydWarshall() {
	for (int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			d[i][j] = mat[i][j];
		}
	}

	//k는 거쳐가는 곳, i는 출발하는 곳, j는 거쳐가는 곳
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (d[i][k] + d[k][j] < d[i][j]) { //거쳐가는 것이 현재 입력된 값보다 작으면
					d[i][j] = d[i][k] + d[k][j]; //갱신
				}
			}
		}
	}
}

int main() {
	setting();
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int a, b;//a사건, b사건
		scanf("%d %d", &a, &b);
		mat[a][b] = 1; //a사건이 b사건보다 앞에 있고 이것을 1로 표현
	}
	FloydWarshall();
	cin >> s;

	//사건의 관계를 알고 싶다.
	for (int i = 0; i < s; i++) {
		int x, y; //x사건, y사건
		scanf("%d %d", &x, &y);
		if (d[x][y] != INF) {
			cout << -1 << '\n';
		}
		else if (d[y][x] != INF) {
			cout << 1 << '\n';
		}
		else {
			cout << 0 << '\n';
		}
	}
}