728x90
반응형
1613번: 역사
문제
https://www.acmicpc.net/problem/1613
풀이
여러 사건의 선후 관계를 판단하는 문제다. 플로이드-워셜 알고리즘을 사용해 풀 수 있다. a가 b보다 먼저 일어났다고 할 때 dist[a][b] = 1, 나머지는 INF로 플로이드를 돌린다. 그리고 x, y의 선후 관계를 알고 싶을 때, dist[x][y]가 INF가 아니라면 x가 먼저 일어난 일이고(-1 출력), INF면 x가 먼저 일어난 일은 아니다. 이때 dist[y][x]가 INF가 아니면 y가 먼저 일어난 일이고(1 출력), INF면 어떤지 모르는(유추할 수 없는, 0 출력) 상황이다.
코드
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, K, dist[401][401], S;
cin >> N >> K;
// dist 배열 초기화
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
dist[i][j] = i == j ? 1 : INF;
// 간선 입력
while (K--) {
int a, b;
cin >> a >> b;
dist[a][b] = 1;
}
// 플로이드 워셜
for (int k = 1; k <= N; k++)
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
// 출력
cin >> S;
while (S--) {
int a, b;
cin >> a >> b;
if (dist[a][b] != INF)
cout << -1;
else if (dist[b][a] != INF)
cout << 1;
else
cout << 0;
cout << '\n';
}
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 13168 내일로 여행 (0) | 2023.02.25 |
---|---|
[백준 / BOJ] C++ 1956 운동 (0) | 2023.02.25 |
[백준 / BOJ] C++ 1389 케빈 베이컨의 6단계 법칙 (0) | 2023.02.25 |
[백준 / BOJ] C++ 11403 경로 찾기 (0) | 2023.02.25 |
[백준 / BOJ] C++ 11404 플로이드 (0) | 2023.02.25 |