[BOJ1613] 역사 (플로이드 워셜)알고리즘/최단 경로2023. 9. 3. 16:09
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/1613
문제 풀이
- 단방향 그래프
- 주어진 입력에 따라 인접 행렬을 초기화 및 입력 가중치(1) 설정
- 플로이드 워셜 알고리즘을 실행해서, 각 노드별로 다른 노드 갈 수 있는지 구한다.
- 시간 복잡도 : O(N)
각 케이스에 대해
1) 0 인 경우는 (i, j), (j, i) 둘다 INF로 확인 불가를 뜻함 // 입력
2) 1 인 경우 j와 i 두 값중 i 사건이 더 먼저 발생한 경우를 뜻함
현재 단방향 그래프로 풀이했기 때문에 (i, j)로 갈 수 없고, (j, i)가 양수인 경우를 나타낸다
3) -1인 경우 i와 j 두 값중 i 사건이 더 먼저 발생한 경우를 뜻함
현재 단방향 그래프로 생각하여 풀이 했기 때문에 (i, j)의 값이 INF가 아니고 양수인 경우, 즉 i 에서 j로 갈수 있는 경우를 나타낸다
예제 입력
5 5
1 2
1 3
2 3
3 4
2 4
3 // 구하려 하는 쿼리 수
1 5
2 4
3 1
플로이드 워셜 수행 결과
0 | 1 | 1 | 2 | INF |
INF | 0 | 1 | 1 | INF |
INF | INF | 0 | 1 | INF |
INF | INF | INF | 0 | INF |
INF | INF | INF | INF | 0 |
- (1, 5) 의 경우 (1,5) , (5,1) 둘다 INF이기 때문에 답은 0이다
- (2, 4)의 경우 (2, 4) 갈 수 있으므로 2가 4보다 먼저이므로, 답은 -1 이다
- (3, 1) 의 경우 (3,1) == INF이고, (1,3) = 1 이므로, 1이 3보다 먼저이므로 답은 1이다
참고. https://steady-coding.tistory.com/99
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int n, k, s;
static int[][] floyd;
static int INF = 160001;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 사건의 개수
k = Integer.parseInt(st.nextToken()); // 전 후 관계 수
floyd = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++) {
Arrays.fill(floyd[i], INF);
floyd[i][i] = 0;
}
for(int i = 1; i <= k; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
floyd[v1][v2] = 1;
}
pro(); // 플로이드 워셜 실행
s = Integer.parseInt(br.readLine());
while(s > 0) {
s -= 1;
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
int result = 0;
if(floyd[v1][v2] != INF && floyd[v1][v2] != 0) result = -1;
else if(floyd[v2][v1] != INF && floyd[v2][v1] != 0) result = 1;
sb.append(result).append("\n");
}
System.out.println(sb);
}
static void pro() {
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
}
}
}
}
public static void main(String[] args) throws Exception {
input();
}
}
반응형
'알고리즘 > 최단 경로' 카테고리의 다른 글
[BOJ13424] 비밀 모임 (플로이드 워셜, 최단 경로) (0) | 2023.09.04 |
---|---|
[BOJ17182] 우주 탐사선 (플로이드 워셜, 완전탐색) (1) | 2023.09.04 |
[BOJ1507] 궁금한 민호 (플로이드 워셜) (1) | 2023.09.03 |
[BOJ2660] 회장뽑기 (플로이드 워셜, 최단거리) (0) | 2023.09.02 |
[BOJ1956] 운동 (플로이드 워셜) (0) | 2023.09.02 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!