[백준] 1865번: 웜홀 - 자바(JAVA)

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

1865번: 웜홀

 

문제 해석

N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 존재합니다.

도로에는 방향이 없으며 웜홀에는 방향이 존재합니다.

 

웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로입니다.

도착을 하게 되면 시작 했을 때보다 시간이 뒤로 가게 됩니다.

 

이때 한 지점에서 출발하여 시간여행을 하여 다시 출발하였던 위치로 돌아왔을 때 출발하였을 때 보다 시간이 되돌아가는 경우가 있는지 확인하는 프로그램을 작성하세요

 

S , E , T 로 도로의 정보가 주어집니다.

S와 E는 연결된 지점의 번호

T는 도로를 통해 이동하는게 걸리는 시간을 의미합니다.

 

첫번째줄에는 TC의 개수가 주어집니다.

각 테스트의 첫번째 줄에는 지점의 수 N, 도로의 개수 M, 원홈의 개수 W가 주어집니다.

 

2번째 줄부터 M+1번째 줄까지 도로의 정보가 주어집니다.

M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 주어집니다.

시작 지점, 도착 지점, 줄어드는 시간을 의미합니다.

 

문제 풀이 전 설계

간선에 양의 weight가 주어집니다.

최단경로를 사용해야 할 것 같아 greedy 하게 방문하는 활용한 다익스트라가 떠오릅니다.

 

다익스트라, 플로이드 와샬 알고리즘을 통해 정점 i로부터 j까지의 최단 경로를 구합니다.

 

이후로 다음과 같은 로직을 구사하면 될 것 같습니다.

//도로의 개수
for(int i=0; i<500; i++){
	//웜홀의 개수
	for(int j=0; j<200; j++){
    	if(도로 i에서 웜홀 j로 가는 비용 > 웜홀 j로 통해 이동한 곳에서 도로 i까지 되돌아 가는 비용){
        	continue;
        }
        return "YES"
    }
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_1865_웜홀 {

    static int INF = 500_000_1;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        out:
        while (tc-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            int[][] time = new int[N + 1][N + 1];

            for (int i = 1; i <= N; i++) {
                Arrays.fill(time[i], INF);
            }
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());

                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());

                time[S][E] = Math.min(time[S][E], T);
                time[E][S] = Math.min(time[E][S], T);

            }

            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());

                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());

                time[S][E] = Math.min(time[S][E], -T);
            }

            for (int k = 1; k <= N; k++) {
                for (int i = 1; i <= N; i++) {
                    if (i == k) continue;
                    for (int j = 1; j <= N; j++) {
                        if (i == j || j == k) continue;
                        time[i][j] = Math.min(time[i][j], time[i][k] + time[k][j]);
                    }
                }
            }


            for (int i = 1; i <= N; i++) {
                if (time[i][i] < 0) {
                    System.out.println("YES");
                    continue out;
                }

                for (int j = 1; j <= N; j++) {
                    if (i == j) continue;
                    if (time[i][j] == INF || time[j][i] == INF) continue;
                    if (time[i][j] + time[j][i] < 0) {
                        System.out.println("YES");
                        continue out;
                    }
                }
            }
            System.out.println("NO");
        }

    }
}