신호 라우팅 풀이

• 문제(알고스팟): https://algospot.com/judge/problem/read/ROUTING
• 제한시간: 2초

문제에서 주의할 점

• 최악의 case: node 수 10000, edge 수 20000
  • 2차원 배열로 graph정보를 표현하면 10000 * 10000 = 1억 (약 1초)
  • 따라서 graph을 인접행렬이나, hash-map와 같이 다른 형태의 표현이 필요.
    • node 10000 + edge 20000 해서 3만 정도의 루프로 graph 표현
• 간선의 dist값(거리값) 이 이 문제에서는 noise로 되어 있고, 증폭 (곱셉) 연산을 필요로 함
  • double 형 사용이 필요
  • 누적테이블에서, 비교시 덧셈이 아니라 곱셉을 한다음 비교 필요.
  • 최초 노드 (시작노드)를 0 이 아니라 1로 초기화 필요. (0을 곱하면 0이되니까....)
• 시작 노드 0 으로 고정, 원하는 답(target)노드는 마지막 노드로 고정
• 출력시 소수점 밑 열자리까지 출력하기를 원함 (System.out.printf("%.10f", result)) 포멧팅 필요

최단경로를 찾는 문제, 음수는 없고, 시작 -> 끝 이 있음으로, 다익스트라로 풀이 가능

풀이코드

Java로 풀이함

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class NoiseCalc {
    int nodeNum;
    ArrayList<ArrayList<Edge>> nodeList;
    int visited[], path[];
    double noiseVal[];
    double INFINITY = Double.MAX_VALUE;
    int VISITED = 1;

    public NoiseCalc(int nodeNum, ArrayList<ArrayList<Edge>> nodeList) {
        super();
        this.nodeNum = nodeNum;
        this.nodeList = nodeList;

        this.visited = new int[nodeNum];
        this.noiseVal = new double[nodeNum];
        Arrays.fill(this.noiseVal, INFINITY);
        this.path = new int[nodeNum];
        Arrays.fill(this.path, -1);
    }

    public double runCalc() {
        // start 는 0번 node로 고정
        int START_NODE_ID = 0;

        this.noiseVal[START_NODE_ID] = 1; // 여기를 1로 하면 곱셉해도 자기자신
        this.path[START_NODE_ID] = 0;

        PriorityQueue<Node> q = new PriorityQueue<Node>();
        q.offer(new Node(START_NODE_ID, this.noiseVal[START_NODE_ID]));

        while (!q.isEmpty()) {
            Node n = q.poll();

            // 가지치기, q에서 꺼내온 노드의 Noise누적값이 기록된거보다 크면, 방문할 필요가 없음.
            if (n.noise > this.noiseVal[n.id]) {
                continue;
            }

            // 현재 노드에서 방문 가능한 노드를 모두 체크,
            // 즉 현재 노드에서 방문가능한 edge을 모두 체크
            ArrayList<Edge> neerList = this.nodeList.get(n.id);
            for (int i = 0; i < neerList.size(); i++) {
                Edge edge = neerList.get(i);

                double nuVal  = this.noiseVal[edge.endNodeId];
                double newVal;

                newVal = this.noiseVal[n.id] * edge.noiseVal;

                if (nuVal > newVal) { // 더 최적값이 있으면.
                    // 누적테이블 갱신
                    this.noiseVal[edge.endNodeId] = newVal;

                    // 경로 갱신
                    this.path[edge.endNodeId] = n.id;

                    // 해당 노드는 큐에 넣어서, 그 노드에서 부터 방문하는 곳을 계산해야함
                    q.offer(new Node(edge.endNodeId, newVal));
                }
            }
        }

        return this.noiseVal[this.nodeNum - 1];
    }
}

class Node implements Comparable<Node> {
    public int id;
    public double noise;

    Node(int id, double noise) {
        this.id = id;
        this.noise = noise;
    }

    @Override
    public int compareTo(Node o) {
        return this.noise <= o.noise ? -1 : 1;
    }

    @Override
    public String toString() {
        return "Node [id=" + id + ", noise=" + noise + "]";
    }
}

class Edge {
    public int startNodeId, endNodeId;
    public double noiseVal;

    public Edge(int sNodeId, int eNodeId, double noiseVal) {
        this.startNodeId = sNodeId;
        this.endNodeId = eNodeId;
        this.noiseVal = noiseVal;
    }

    public String toString() {
        return "(" + this.startNodeId + "->" + this.endNodeId + ") : [" + this.noiseVal + "]";
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        InputStreamReader fr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(fr);

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

            int nodeNum = Integer.parseInt(st.nextToken());
            int edgeNum = Integer.parseInt(st.nextToken());

            ArrayList<ArrayList<Edge>> nodeList = new ArrayList<ArrayList<Edge>>(nodeNum);
            // 그래프를 만드는데 최악의 경우 3만번 정도...
            for (int nIndex = 0; nIndex < nodeNum; nIndex++) { // 10000
                nodeList.add(new ArrayList<Edge>());
            }
            for (int e = 0; e < edgeNum; e++) { // 20000
                StringTokenizer edgeStrToken = new StringTokenizer(br.readLine());

                int nodeAId = Integer.parseInt(edgeStrToken.nextToken());
                int nodeBId = Integer.parseInt(edgeStrToken.nextToken());
                double noiseVal = Double.parseDouble(edgeStrToken.nextToken());

                ArrayList<Edge> nodeAEdges = nodeList.get(nodeAId);
                ArrayList<Edge> nodeBEdges = nodeList.get(nodeBId);

                nodeAEdges.add(new Edge(nodeAId, nodeBId, noiseVal));
                nodeBEdges.add(new Edge(nodeBId, nodeAId, noiseVal));
            }

            NoiseCalc calc = new NoiseCalc(nodeNum, nodeList);
            double result = calc.runCalc();

            System.out.printf("%.10f\n", result);
        }

        fr.close();
        br.close();
    }

}