BOJ | Gold 4/11657/타임머신

본 문제는 벨만 포드 알고리즘 개념으로 해결할 수 있는 최단경로문제입니다. 벨만 포드 알고리즘에 대한 개념은 아래 링크로 확인해주시고, 문제를 바로 풀어보도록 하겠습니다.
2023.07.14 - [개발/Dev | 알고리즘] - 최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로

최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로

 

1. 문제 이해

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, (1) A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. (2) 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

(3) 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

(1) 시작, 도착, 걸린 시간이라는 키워드를 통해 방향이 존재하고, 방향에는 가중치가 시간으로 부여되어 있다는 점을 알 수 있습니다.
(2) 시간이 음수인 경우가 있다는 점에서 음의 가중치를 가진 경우에 사용하는 알고리즘을 적용해야 한다는 것을 알 수 있습니다.
(3) 1번 도시를 기준으로 나머지 도시까지 모두 방문한다는 점에서 벨만-포드 알고리즘을 사용하기에 적합하다는 것을 알 수 있습니다.
위 문제를 통해 최단 경로 문제로 접근해야 한다는 것을 알 수 있고, 음의 가중치가 존재하는 경우에도 사용할 수 있는 벨만-포드 알고리즘을 적용해야 함을 알 수 있습니다.
 
 

2. 로직

2-1) 로직 플로우
시작점을 제외하고 INF로 할당된 모든 지점에 대해 최단 경로 값이 존재하면 그 값을 할당하고, 연결된 간선이 없는 경우에는 그대로 INF로 두면 됩니다. 노드 + 1회의 반복 후에 음수 사이클이 발생하는 경우를 확인 했다면, 음수 사이클이 없는 경우에는 각 지점에 대해서 가장 빠른 시간을 출력합니다. 시작 지점인 1번을 제외한 2번부터 출력합니다. 그런데 이때, INF로 할당된 시간에 대해서는 "-1"로 출력하는 조건을 추가합니다. 만약 음수 사이클이 존재하는 경우라면 "-1"을 출력합니다.
2-2 ) 로직 상세
1) 입력 받은 데이터를 통해 간선 정보를 저장하는 배열 생성 후 간선 정보를 저장함
2) 각 지점에 대한 최단 시간을 저장할 dist 배열을 선언하고, 노드 수 + 1만큼 길이를 지정한 뒤, 모든 값에 INF를 할당함
3) 각 노드와, 각 지점에 대해 최단 시간을 구하기 위한 이중 for문을 사용하고, dist에 할당된 값보다 현재 가중치가 더 작은 경우 이를 값에 할당함.
4) dist 배열이 N(i가 N인 경우)번째에도 갱신되는 경우가 발생한다면, 음수 사이클이 존재하는 경우이므로(값이 계속 작아짐) 이 경우에는 최단 경로를 구할 수 없는 경우라는 조건을 로직에 반영한다.
5) 음수 사이클이 존재하는 경우에는 -1을 출력하고, dist 배열에 저장된 최단 경로를 값으로 출력한다. 이때 INF가 할당된 경우에는 -1을 출력한다.
 

3. 구현

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

public class Main {
    static int N, M;
    static Edge[] edge;
    static StringBuffer sb;
    final static int INF = (int)1e9;

    static class Edge {
        int from;
        int to;
        int time;

        public Edge(int from, int to, int time) {
            this.from = from;
            this.to = to;
            this.time = time;
        }
    }

    public static boolean bellmanFord(Edge[] edge, int start) {
        long[] dist = new long[N + 1];
        for (int i = 1; i < N + 1; i++) {
            dist[i] = INF;
        }

        dist[start] = 0;

        boolean isMinusCycle = false;
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < M; j++) {
                Edge cur = edge[j];

                if (dist[cur.from] == INF) {
                    continue;
                }

                if (dist[cur.to] > dist[cur.from] + cur.time) {
                    dist[cur.to] = dist[cur.from] + cur.time;

                    if (i == N) {
                        isMinusCycle = true;
                    }
                }
            }
        }

        sb = new StringBuffer();
        if (!isMinusCycle) {
            for (int i = 2; i < N + 1; i++) {
                if (dist[i] == INF) {
                    sb.append("-1\n");
                } else {
                    sb.append(dist[i] + "\n");
                }
            }
        }

        return isMinusCycle;
    }

    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());

        edge = new Edge[M];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            edge[i] = new Edge(from, to, weight);
        }


        if (bellmanFord(edge, 1)) {
            System.out.println("-1");
        } else {
            System.out.print(new String(sb));
            sb.setLength(0);
        }
    }
}

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

11657번: 타임머신

직접 문제를 풀어봄으로써 위 내용을 확인하셨으면 좋겠습니다. 감사합니다 :)