[백준] 알고리즘 분류(그래프 이론,JAVA)1865번, 웜홀

문제 링크

1865번: 웜홀

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 도로는 양방향, 웜홀은 단방향으로 이루어집니다.

2. 웜홀을 사용하여 이동하면 시간이 감소합니다.

3. 임의의 지역에서 출발하여 출발 위치의 도착할 때 시간이 되돌아갔으면 YES, 아니면 NO을 결과로 출력합니다.

4. 각 지역을 연결하는 도로가 중복될 수 있습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 벨만 포드 알고리즘을 이용하여 음수 싸이클이 존재하는지 확인합니다.

 

3. 음수 싸이클 존재하면 YES, 아니면 NO를 결과로 출력합니다.

 

벨먼 포드 알고리즘!

 

벨먼-포드 알고리즘 - 위키백과, 우리 모두의 백과사전

 

벨먼 포드 알고리즘은 정점을 이동시 음수의 Value값이 존재할 때 최단 거리를 구할 수 있는 알고리즘입니다.

 

최단 거리와 더불어 음수 싸이클이 존재할 수 있는 것을 확인할 수 있습니다.

 

벨먼 포드 알고리즘은 (N-1)번 탐색하여 각 지역에 최단 거리를 구합니다.

 

음수 싸이클이 존재하는 것을 확인할 때

 

(N-1)번 탐색한 뒤, 1번 더 탐색하여 최단 거리의 값이 변경되면 음수 싸이클이 존재하는 것을 확인할 수 있습니다.

 

이 문제에서 결과로 출력하라고 하는 내용을 생각해보면, 음수 싸이클이 존재하는지 확인하라는 내용입니다.

 

 

 

 

출발 위치의 도착할 때 시간이 되돌아갔다 == 음수 싸이클 존재한다.

 

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

※2번째 테스트 케이스만 진행하겠습니다.

 

N : 3

M : 2

W : 1

 

2. 벨만 포드 알고리즘을 이용하여 음수 싸이클이 존재하는지 확인합니다.

 

 

시작 지역 1번일 때!

 

	지역1	지역2	지역3
최단 거리	0	INF	INF

 

	지역1	지역2	지역3
최단 거리	0	3	INF

	지역1	지역2	지역3
최단 거리	0	3	7

	지역1	지역2	지역3
최단 거리	-1	3	7

 

.....

 

	지역1	지역2	지역3
최단 거리	-9	2	6

 

(N-1)번을 탐색한 뒤,  탐색 1번을 더 진행하여 음수 싸이클이 존재하는지 확인합니다.

 

	지역1	지역2	지역3
최단 거리	-9	-6	6

최단 거리가 변경되었기 때문에 음수 싸이클 존재!

 

3. 음수 싸이클 존재하면 YES, 아니면 NO를 결과로 출력합니다.

 

음수 싸이클 존재하므로

YES 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 길, 웜홀 등 띄어쓰기 기준 나누었습니다.
• bellman함수를 이용해서 각 지역에서 시작할 때 음수 싸이클이 존재하는지 확인합니다.
• 음수 싸이클이 존재하면 YES, 없으면 NO를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bellman함수는 벨먼-포드 알고리즘을 이용하여 음수 사이클이 존재하는지 확인합니다.

 

결과코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    //도로 및 포탈의 정보 관련 클래스
    static class node{
        int position, time;
        public node(int position, int time) {
            this.position = position;
            this.time = time;
        }
    }
    static final int MAX_VALUE = 25000001;	//나올 수 있는 최대 시간 + 1 값
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] distance;
        ArrayList<ArrayList<node>> graph;
        //각 테스트케이스 진행!
        for(int test_case = 0;test_case<t;test_case++) {
            st = new StringTokenizer(br.readLine()," ");
            graph = new ArrayList<>();
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            for(int i=0;i<=N;i++)
                graph.add(new ArrayList<>());

            //도로에 대한 정보 저장
            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());
                graph.get(S).add(new node(E, T));
                graph.get(E).add(new node(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());
                graph.get(S).add(new node(E, T * -1));
            }
            distance = new int[N+1];
            boolean check = false;
            //각 지역을 시작으로 벨먼 포드 진행!
            for(int i=1;i<=N;i++){
                //음수 싸이클 존재할 때
                if(bellman(i, distance, graph, N)){
                    bw.write("YES\n");		//YES BufferedWriter 저장
                    check = true;
                    break;
                }
            }
            if(!check)		//음수 싸이클 존재 X
                bw.write("NO\n");		//NO BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //벨먼 포드 알고리즘으로 음수 싸이클 존재하는지 확인하는 함수
    static boolean bellman(int start, int[] distance, ArrayList<ArrayList<node>> graph, int N) {
        boolean check = false;
        Arrays.fill(distance, MAX_VALUE);	//거리 배열 MAX_VALUE로 초기화
        distance[start] = 0;	//시작 지역 0으로 초기화
        //(N-1)번 최단 거리 탐색!
        for (int i = 1; i < N; i++) {
            check = false;
            for (int j = 1; j <= N; j++) {
                for (node next : graph.get(j)) {
                    if (distance[j] != MAX_VALUE && distance[next.position] > distance[j] + next.time) {
                        distance[next.position] = distance[j] + next.time;
                        check = true;
                    }
                }
            }
            if (!check)	//더 이상 최단 거리가 존재하지 않을 때 == 음수 사이클 X
                break;
        }
        //(N-1)번 탐색이 종료된 뒤, 음수 사이클이 존재하는지 확인!
        if(check){
            for(int i=1;i<=N;i++)
                for(node next : graph.get(i))
                    //최단 거리가 변경되었기 때문에 음수 사이클 존재!
                    if(distance[i] != MAX_VALUE && distance[next.position] > distance[i] + next.time)
                        return true;
        }
        return false;		//음수 사이클 존재 X
    }
}