풀이 방법
그 동안 거의 모든 문제를 경로가 있으면 값을 주는 방식으로 생각해서 풀이했다.
이 문제는 생각을 좀 바꿔서 접근하는 게 필요했다.
일방통행을 양방향으로 바꾸는 비용을 구하는 문제이기 때문에
양방향 경로는 0, 일방통행 경로가 있으면 0을 주고 반대쪽으로는 1을 줘서 필요한 비용을 계산했습니다.
(자기 자신으로는 무조건 갈 수 있기 때문에 0을 준다.)
내 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, K, u, v, b;
static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N + 1][N + 1];
for (int i = 0; i < N + 1; i++) {
Arrays.fill(arr[i], 1000000);
arr[i][i] = 0;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
arr[u][v] = 0;
arr[v][u] = (b == 0) ? 1 : 0;
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
for (int q = 1; q < N + 1; q++) {
if (j == q)
continue;
arr[j][q] = Math.min(arr[j][q], arr[j][i] + arr[i][q]);
}
}
}
K = Integer.parseInt(br.readLine());
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
System.out.println(arr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]);
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
월드컵 - 6987번 (0) | 2022.01.24 |
---|---|
간선 이어가기2 - 14284번 (0) | 2022.01.21 |
회문 - 17609번 (0) | 2021.12.30 |
해킹 -10282번 (0) | 2021.12.29 |
소수 화폐 (0) | 2021.12.29 |