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

문제 링크

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

1865번: 웜홀

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 도로와 웜홀의 정보를 바탕으로 전체 지점간의 이동 cost를 저장하는 2차원 배열을 초기화
2. 이후 해당 배열을 바탕으로 플로이드-와샬 알고리즘을 통해 전체 최단거리 cost를 계산
3. 그 다음 2차원 배열 속 (i, i) 지점을 돌며 해당 지점이 음수 값이 있는 지를 통해 시간이 줄어들며 출발 위치로 돌아올 수 있는 지를 확인 후 배열에 답을 저장

 우선 크게 문제를 보았을 때 지점 간의 이동 cost에 대해 음수가 존재하는 문제이기에, 지점들간의 최단 거리를 계산하는 알고리즘 중 음수값이 존재해도 이를 계산할 수 있는 알고리즘을 적용해야 한다.

 처음에는 벨만-포드 알고리즘을 떠올렸지만 이를 통해 문제를 해결한 적이 없어 다른 방법이 있는 지 고민하다가, 플로이드-와샬 알고리즘 또한 음수 사이클의 여부를 판단할 수 있다는 글을 보고 이를 문제 해결에 적용했다. 결국 기존의 플로이드-와샬 알고리즘을 적용하는 것처럼 이동 cost를 모아놓은 2차원 배열을 3중 반복문으로 계산을 하면 되는데, 이후 결과 2차원 배열에서 자기 자신으로 돌아올 때 필요한 cost를 저장하는 (i, i) 위치의 값이 음수이면 음수 사이클이 존재함을 알아낼 수 있다.

 물론 문제에서 요구하는 건 특정 위치에서의 음수 사이클이 존재하는 지를 묻는 것이 아닌 임의 지점에서 음수 사이클이 가능한 지를 묻기 때문에, 각 모든 지점에서 한 번이라도 음수 사이클이 발견되면 YES를, 아니면 NO를 답에 저장해 이후 출력하면 된다.

 

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        ArrayList<String> answers = new ArrayList<>();

        for (int i = 0; i < T; i++) {
            int N, M, W, p1, p2, cost;
            st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());//지점의 개수
            M = Integer.parseInt(st.nextToken());//도로의 개수
            W = Integer.parseInt(st.nextToken());//웜홀의 개수

            int[][] dist = new int[N + 1][N + 1];//cost 비용 2차원 배열
            for (int j = 0; j < N + 1; j++) {
                Arrays.fill(dist[j], 987654321);
                dist[j][j] = 0;
            }

            for (int j = 0; j < M; j++) {//도로
                st = new StringTokenizer(br.readLine());

                p1 = Integer.parseInt(st.nextToken());
                p2 = Integer.parseInt(st.nextToken());
                cost = Integer.parseInt(st.nextToken());

                if (cost < dist[p1][p2]) {
                    dist[p1][p2] = cost;
                    dist[p2][p1] = cost;
                }
            }

            for (int j = 0; j < W; j++) {//웜홀
                st = new StringTokenizer(br.readLine());

                p1 = Integer.parseInt(st.nextToken());
                p2 = Integer.parseInt(st.nextToken());
                cost = Integer.parseInt(st.nextToken()) * -1;

                dist[p1][p2] = cost;
            }

            for (int j = 1; j <= N; j++) {//플로이드-와샬
                for (int k = 1; k <= N; k++) {
                    for (int l = 1; l <= N; l++) {
                        dist[k][l] = Math.min(dist[k][l], dist[k][j] + dist[j][l]);
                    }
                }
            }

            for (int j = 1; j <= N; j++) {//dist[j][j] 중 음수가 있는 지 확인
                if (dist[j][j] < 0) {
                    answers.add("YES");
                    break;
                }

                if (j == N) {
                    answers.add("NO");
                }
            }
        }

        for (int i = 0; i < T; i++) {//답 출력
            System.out.println(answers.get(i));
        }
    }
}

결과