글 읽기 - 우선순위큐를 이용했을 때 시간이 더 걸리는 이유??

qls0860 5년 전 0

선행 탐색을 하면서 가까운 노드부터 탐색해 갱신하는 코드랑

우선순위큐를 이용해 갱신하는 코드를 제출했는데요.

전자는 464ms 후자는 556ms로

이상하게 후자가 더 오래 걸렸어요. 이유가 뭐죠? ㄷㄷ

/////////// 선형 탐색을 이용한 다익스트라 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	
	static int n, m, city[][], d[], max = (int)1e9, start, end;
	static boolean[] visit;
	
	static int smallIndex() { // d배열에서 방문 안하고 가장 작은 값을 가진 인덱스 return
		int idx = 0, ans = max;
		
		for (int i=1; i<=n; i++) {
			if (d[i] < ans && !visit[i]) {
				ans = d[i];
				idx = i;
			}
		}
		
		return idx;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		city = new int[n+1][n+1];
		d = new int[n+1];
		visit = new boolean[n+1];

		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++) 
				if (i != j)
					city[i][j] = max;
		
		for (int i=0; i<m; i++) {
			String[] s = br.readLine().split(" ");
				int x = Integer.parseInt(s[0]);
				int y = Integer.parseInt(s[1]);
				int c = Integer.parseInt(s[2]);
				if (c < city[x][y])
					city[x][y] = c;
		}
		
		String[] s = br.readLine().split(" ");
		start = Integer.parseInt(s[0]);
		end = Integer.parseInt(s[1]);
        // 입력
		
		for (int i=1; i<=n; i++) {
			if (city[start][i] != 0) d[i] = city[start][i];
			else d[i] = max;
		} // d 배열 초기화
			
		d[start] = 0;
		visit[start] = true;
		
		for (int i=0; i<n-2; i++) {
			int cur = smallIndex();
			visit[cur] = true;
			for (int j=1; j<=n; j++) {
			
				if (!visit[j] && d[cur] + city[cur][j] < d[j]) {
					d[j] = d[cur] + city[cur][j]; // 다익스트라 로직
				}
			}
		}
		System.out.println(d[end]);
	}
}
/////////// 

/////////// 우선순위 큐를 이용한 다익스트라 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
	
	static int n, m, start, end ,d[], INF = (int)1e9;
	static List<Element>[] a;
	static PriorityQueue<Element> pq = new PriorityQueue<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		d = new int[n+1];
		a = new List[n+1];
		
		for (int i=1; i<=n; i++) {
			a[i] = new ArrayList<>();
			d[i] = INF;
		}
		
		for (int i=0; i<m; i++) {
			String[] s = br.readLine().split(" ");
				int x = Integer.parseInt(s[0]);
				int y = Integer.parseInt(s[1]);
				int c = Integer.parseInt(s[2]);
				a[x].add(new Element(y,c));
		}
		
		String[] s = br.readLine().split(" ");
		start = Integer.parseInt(s[0]);
		end = Integer.parseInt(s[1]);
        // 입력
		
		d[start] = 0;
		pq.add(new Element(start,0));
		
		while(!pq.isEmpty()) {
			Element cur = pq.poll();
			
			if (d[cur.node] < cur.distance) continue; // 중복 거름
			
			for (int i=0; i<a[cur.node].size(); i++) {
				int next = a[cur.node].get(i).node;
				int nextDistance = d[cur.node] + a[cur.node].get(i).distance;
				
				if (nextDistance < d[next]) { // 다익스트라 로직
					d[next] = nextDistance;
					pq.add(new Element(next, nextDistance));
				}
			}
		}
		
		System.out.println(d[end]);
	}
}

class Element implements Comparable<Element> {
	int node, distance;

	public Element(int node, int distance) {
		this.node = node;
		this.distance = distance;
	}

	@Override
	public int compareTo(Element o) { // 거리가 짧은 노드 먼저 올라오게 비교
		if (this.distance > o.distance) return 1;
		else if (this.distance == o.distance) return 0;
		else return -1;
	}
	
}

startlink 5년 전 0

O(V^2) vs O(ElgE) 과연 그 승자는?

qls0860 5년 전 0

후자가 빠른 거 아닌가요?

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

문제

문제

출처

ICPC

우선순위큐를 이용했을 때 시간이 더 걸리는 이유??

qls0860 5년 전 0

startlink 5년 전 0

qls0860 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말