글 읽기 - [java] 우선순위큐 사용 다익스트라 런타임 에러 문제 ㅠ.ㅠ

kisrin4319 7년 전 0

최단경로 문제를 우선순위큐를 사용한 다익스트라 알고리즘으로 해결하려고 하는데 자꾸 런타임 에러가 발생합니다.

다른 분들의 질문도 읽어보았고, 역시 마찬가지로 메모리 폭발이 문제가 아닐까 추측하고 있습니다.

제 생각은 대략 40~50 라인에서 메모리가 초과 나는것 같은데 도저히 해결 방법을 모르겠어서 도움을 부탁드립니다

public class Main {

	public static PrintWriter out;
	static int[][] ad;
	static boolean[] visited;
	static int dist[];
	static int INF = (int) 98765432;
	static int V;
	static int E;
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));
		V = sc.nextInt();
		E = sc.nextInt();
		int Start = sc.nextInt();
		ad = new int[V+1][V+1];
		visited = new boolean[V+1];
		dist = new int[V+1];
		
		for(int i=0;i<=V;i++)
		{
			dist[i] = INF;
		}
		for(int i=0;i<E;i++)
		{
			int t1 = sc.nextInt();
			int t2 = sc.nextInt();
			int t3 = sc.nextInt();
			ad[t1][t2]=t3;
		}
		
		dijkstra(Start);
		out.close();
	}
	private static void dijkstra(int start) {
		PriorityQueue<Element> q = new PriorityQueue<Element>();
		dist[start] =0;
		q.offer(new Element(start,dist[start]));
		
		while(!q.isEmpty()){
			int cost = q.peek().getDistance();
			int here = q.peek().getIndex();
			q.poll();
			if(cost>dist[here])
				continue;
					
			for(int i=0;i<=V;i++){
				if(ad[here][i]!=0 && dist[i] > dist[here]+ad[here][i]){
					dist[i] = dist[here]+ad[here][i];
					q.offer(new Element(i,dist[i]));
				}
			}
		}
		for(int i=1;i<=V;i++){
			out.println(dist[i] ==INF ? "INF" : dist[i]);
		}
	}
}

class Element implements Comparable<Element>{
	private int index;
	private int distance;
	
	Element(int index, int distance){
		this.index = index;
		this.distance = distance;
	}
	
	public int getIndex(){
		return index;
	}
	public int getDistance(){
		return distance;
	}
	
	public int compareTo(Element o){
		return distance <=o.distance ? -1 :1;
	}
}

chogahui05 7년 전 0

16번째 줄이 메모리 초과 원인입니다.

2차원 배열을 선언하시지 마시고 Vector라던지, 희소 행렬을 선언해서 관리하는 게 어떨까요?

kisrin4319 7년 전 0

조언 감사합니다. 다른 분의 코드를 참조하여 ArrayList 로 구현해서 통과했습니다.(이것도 약간 어거지로 통과한 느낌)

하지만 Vector 라던가, 희소행렬로 구현하려고 하니 응용력이 부족한건지 잘 모르겠네요 ㅠ.ㅠ

chogahui05 7년 전 0

ArrayList나 Vector로 구현하는 게 쉽습니다. 코드도 간결하고요.

c++엔 대표적인 클래스 중 하나가 vector가 있는데요.

java의 ArrayList랑 비슷하다고 보시면 됩니다.

어짜피, 다익스트라에 들어가는 건 가중치 합에 대한 것이니까요.

c로 구현하지 않는 이상 굳이 어렵게 희소행렬까지 생각하실 필요는..

희소 행렬은 단순히 공간 아끼기 위해서

counting sort 방식 + a를 이용해서 구현한다고 보시면 됩니다.

kisrin4319 7년 전 0

쉬운 dfs,bfs 문제를 접하고 해결법을 알았을때 이젠 다 풀수 있겠구나 했는데 배우면 배울수록 더 많이 알고 깊이 공부해야되는 느낌이네요

chogahui05 7년 전 1

자바에 있는 자료구조가 어떻게 구현되어 있는지만 공부하셔도

여기에 나온 알고리즘의 70% 이상을 공부하실 거 같네요. 오버일려나요..?

근데 사실 ArrayList를 안다면 동적 배열에 대해서 공부를 하신 거고..

Map을 공부하신다면 해싱도 공부하신 거고.. (간혹 가다 Map으로 풀리는 경우도 있습니다. 어려운 것 중에서는요.)

레드 블랙 트리도 공부하신 거고..

간혹 가다가 원형 큐 같은 걸 써야 하는 문제가 나오긴 하지만..

그래도 기본적인 자료구조는 java에 나온 것들만 잘 공부하셔도 무난하게 소화 가능하실 겁니다.

고급 알고리즘은 기초가 탄탄해야 소화 가능하신 거니..

chogahui05 7년 전 0

bfs, dfs 문제가 한없이 어려워 지면

이런 괴물 문제가 됩니다.

https://www.acmicpc.net/proble...

이 문제는 머릿속이 계속 교환되는 느낌을 받으실 겁니다.

이런 기초 알고리즘도 어려워 지면 넘넘 어려워 지는 지라..

kisrin4319 7년 전 0

혹시 괜찮으시다면 2589번의 제 질문도 한번 봐주실수 있을까요?

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.