[G3] 백준 1613번 역사 C++ 플로이드 와샬, 최단 경로

리뷰

 

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

싸이클이 없는 순서 그래프에서 노드간 연결 순서가 앞/뒤에 위치하는지를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• d : 노드간 순서 정보를 저장할 2차원 배열

 

함수

없음

 

 

문제풀이

1. n, m 값을 입력 받고, m개의 간선을 입력 받아 d배열을 초기화한다.
2. 플로이드 와샬 알고리즘을 통해 특정 노드를 거쳐 다른 노드로 가는 순서가 일치하면 두 노드간 순서도 일치시킨다.
3. q값을 입력 받고, q개의 쿼리를 입력 받아 순서 정보를 출력 후 개행문자를 삽입한다.

 

트러블 슈팅

1. 거리합을 통해 0, 음수, 양수로 순서를 표시하려고 시도했다가 WA를 받았다.
2. 순서가 일치하는 경우에만 -1 혹은 1로 갱신하는 로직으로 변경하여 AC를 받았다.

 

참고 사항

1. d의 초기값은 0으로 두고, 초기값으로 되어 있는 경우엔 노드간 순서를 알 지 못하는 경우로 보면 된다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 401;
int n, m, q;
int d[N][N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		d[a][b] = -1;
		d[b][a] = 1;
	}

	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (i == j || d[i][j]) continue;
				if (d[i][k] == -1 && d[k][j] == -1) d[i][j] = -1;
				if (d[i][k] == 1 && d[k][j] == 1) d[i][j] = 1;
			}
		}
	}

	cin >> q;
	while (q--) {
		int a, b; cin >> a >> b;
		cout << d[a][b] << "\n";
	}
}