[알고스팟] 신호 라우팅(ROUTING) - 시간초과

문제: 신호라우팅(ROUTING)

언어: 자바

  이 문제는 다익스트라 알고리즘을 이용해서 풀면 된다. 다익스트라 알고리즘은 그래프가 주어졌을 때, 특정 시작점에서 도착점까지의 최소 비용을 구하는 것이다. 다익스트라 알고리즘에 대한 설명은 다음의 링크로 대체하겠다. 워낙 유명한 알고리즘이니 쉽게 찾을 수 있다.

링크1

링크2

 이 문제는 다익스트라의 최소 비용 문제를 + 에서 *로 바꾼 것인데 이 문제는 시간과 메모리 제약을 해결하는 것이 문제이다. 일단 자바로 풀긴 푼것 같은데, 시간초과 오류가 발생한다.

 

 자바로는 어떻게 더 최적화 할수 있을 것인지, 더 고민이 필요하다.

	import java.util.Comparator;
	import java.util.LinkedList;
	import java.util.Scanner;
	public class Main {
	private class Node implements Comparator<Node>{
	private int mNodeNum=-1;
	private double mWeight=Double.MAX_VALUE;
	public Node(int nodeNum,double weight){
	mNodeNum=nodeNum;
	mWeight=weight;
	}
	@Override
	public int compare(Node o1, Node o2) {
	// TODO Auto-generated method stub
	return (o1.mWeight-o2.mWeight)>0 ? 1:0;
	}
	}
	private LinkedList<Node>[] mNodes;
	private double[] mWeight;
	private boolean[] mVisited;
	private int mNodeNumber;
	public Main(int nodeNumber){
	mNodeNumber=nodeNumber;
	mNodes=(LinkedList<Node>[])new LinkedList[nodeNumber];
	mWeight=new double[nodeNumber];
	mVisited=new boolean[nodeNumber];
	for(int i=0;i<nodeNumber;i++) {
	mNodes[i]=new LinkedList<Node>();
	mWeight[i]=Double.MAX_VALUE;
	mVisited[i]=false;
	}
	}
	public void addEdge(int fromNode,int toNode,double weight){
	Node newNode=new Node(toNode,weight);
	mNodes[fromNode].add(newNode);
	}
	public void calculate(){
	int currentEdge=0;
	mWeight[0]=1;//this is starting point;
	for(int idx=1;idx<mNodeNumber;idx++){
	mVisited[currentEdge]=true;
	while(!mNodes[currentEdge].isEmpty()){
	Node nearNode=mNodes[currentEdge].removeFirst();
	//System.out.println(currentEdge +" > "+nearNode.mNodeNum+" + "+nearNode.mWeight);
	if(nearNode.mWeight*mWeight[currentEdge]<mWeight[nearNode.mNodeNum]) {
	//System.out.println("Update Cal-Weight:"+nearNode.mNodeNum+" from "+ mWeight[nearNode.mNodeNum]+" to "+(nearNode.mWeight*mWeight[currentEdge]));
	mWeight[nearNode.mNodeNum]=nearNode.mWeight*mWeight[currentEdge];
	}
	}
	int nextNode=0;
	double min=Double.MAX_VALUE;
	for(int i=0;i<mNodeNumber;i++){
	if(min>mWeight[i] && mVisited[i]==false) {
	min=mWeight[i];
	nextNode=i;
	}
	}
	currentEdge=nextNode;
	}
	System.out.println(mWeight[mNodeNumber-1]);
	}
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc=new Scanner(System.in);
	int caseCnt=sc.nextInt();
	for(int caseIdx=0;caseIdx<caseCnt;caseIdx++){
	int nodeNum=sc.nextInt();
	int edgeNum=sc.nextInt();
	Main solution=new Main(nodeNum);
	for(int i=0;i<edgeNum;i++) {
	int fromNode=sc.nextInt();
	int toNode=sc.nextInt();
	double weight=sc.nextDouble();
	solution.addEdge(fromNode, toNode, weight);
	solution.addEdge(toNode, fromNode, weight);
	}
	solution.calculate();
	}
	}
	}

view raw Routing.java hosted with ❤ by GitHub