11657번: 타임머신

11657번 타임머신

이 문제는 음수간선이 존재하는 그래프에서 최소비용경로를 구하는 문제로 벨만포드알고리즘을 사용하려고 한다.

• 이 문제는 시작점이 1로 주어져 있다. 1로부터 각 노드까지의 최소비용경로를 찾으라고 하고 있다.
• 문제에서 " 시간을 무한시 오래전으로 되롤릴 수 있다면"이라는 조건은, "음수간선으로 인한 사이클이 존재하여 순환을 계속해서 하게되는경우, - INFINITY값을 얻게 되는 경우"를 의미한다. 즉 음수간선으로 인한 사이클이 존재하는 경우 -1을 출력하라고 하고 있다.
• 해당 도시에 가는 경로가 없는 경우에도 -1을 출력한다. 즉 dist table상 초기값인 경우를 의미한다.

출력초과

• 1. dist table의 type을 int -> long 타입으로 변환 하였다.
• 2. edge(from,to,cost)에서 중복되는 from,to를 가지는 edge가 있을 수 있다는 것을 간과했다.
  • edge(from,to,cost) 에서, 같은 from,to를 갖는 edge를, 더 적은 cost를 갖는 edge정보만을 받는 것으로 수정하였더니 정답이 나왔다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static int INIT_MATRIX = 10001;
    public static long[] dist = new long[500];
    public static int n,m;
    public static int[][] matrix = new int[500][500];
    public static void Setting() 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());
        //Init dist table
        Arrays.fill(dist,Long.MAX_VALUE);
        // Init matrix
        for(int i=0;i<n;i++)
            Arrays.fill(matrix[i],INIT_MATRIX);

        int v1=0,v2=0;
        long c =0;
        for(int i=0;i<m;i++){
            //간선정보 받기
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken())-1;
            v2 = Integer.parseInt(st.nextToken())-1;
            c = Long.parseLong(st.nextToken());
            if(matrix[v1][v2]>c) matrix[v1][v2] = (int)c;
        }

    }
    // if there's cylce  return false
    public static boolean belman(int start){
        dist[start]=0;
        int v1=0,v2=0,c=0;
        // n 번 순회
        for(int i=0;i<n;i++){
            // 모든 edge에 대하여
            for(v1=0;v1<n;v1++){
                for(v2=0;v2<n;v2++){
                    if(matrix[v1][v2]==INIT_MATRIX)continue;
                    if(dist[v1]!=Long.MAX_VALUE && dist[v2]>dist[v1]+matrix[v1][v2])
                    {
                        dist[v2] = dist[v1]+matrix[v1][v2];
                        if(i==n-1) return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        Setting();
        int start =0;
        boolean res = belman(start);

        if(!res) System.out.println(-1);
        else{
            for(int i=1;i<n;i++)
            {
                if(dist[i]==Long.MAX_VALUE) System.out.println(-1);
                else System.out.println(dist[i]);
            }
        }
    }
}

위의 출력초과에 대한 본질적 이유

• 그런데 생각해보니 기존의 문제점은 이거였다.

  public static long[][] edges = new long[6001][3];
  ...
  for(int i=0;i<m;i++){
              //간선정보 받기
              st = new StringTokenizer(br.readLine());
              v1 = Integer.parseInt(st.nextToken())-1;
              v2 = Integer.parseInt(st.nextToken())-1;
              c = Long.parseLong(st.nextToken());
              edges[i][0]=v1;
              edges[i][1]=v2;
              edges[i][2]=c;
          }

  • 차라리 모든 edge 정보를 ArrayList에 담았다면, 모든 edge정보를 순환함에 있어서, (from,to)가 같은 edge중에서도 "제일 적은 cost"를 가진 edge에 대해서도 로직이 돌아가는데
  • 나의 위와 같은 코드는, 그저, (from,to)가 같은 edge정보중 "가장 마지막에 주어지는 edge정보"만을 담게 되는 것이 문제다.
  • 따라서 사실 더 빠르게 하려면, Edge라는 class를 새로 만들어서 하는게 좋을 것 같다

• Edge class를 생성하여 했더니, 200ms정도 시간이 줄어들었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static class Edge{
        int from;
        int to;
        int cost;

        public Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }
    public static int INIT_MATRIX = 10001;
    public static long[] dist = new long[500];
    public static int n,m;
    public static List<Edge> edges = new ArrayList<>();
    public static void Setting() 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());
        //Init dist table
        Arrays.fill(dist,Long.MAX_VALUE);

        int v1=0,v2=0,c=0;
        for(int i=0;i<m;i++){
            //간선정보 받기
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken())-1;
            v2 = Integer.parseInt(st.nextToken())-1;
            c = Integer.parseInt(st.nextToken());
            edges.add(new Edge(v1,v2,c));
        }

    }
    // if there's cylce  return false
    public static boolean belman(int start){
        dist[start]=0;
        int v1=0,v2=0,c=0;
        // n 번 순회
        for(int i=0;i<n;i++){
            // 모든 edge에 대하여
            for (Edge edge : edges) {
                if(dist[edge.from]!=Long.MAX_VALUE && dist[edge.to]>dist[edge.from]+edge.cost){
                    dist[edge.to] = dist[edge.from] + edge.cost;
                    // n 번째에도 update가 되면 음의 간선 순환이 존재
                    if(i==n-1) return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        Setting();
        int start =0;
        boolean res = belman(start);

        if(!res) System.out.println(-1);
        else{
            for(int i=1;i<n;i++)
            {
                if(dist[i]==Long.MAX_VALUE) System.out.println(-1);
                else System.out.println(dist[i]);
            }
        }
    }
}