글 읽기 - 자바 시간 초과 질문이요

chldntjr1211 3년 전 0

처음 다익스트라를 이용해 최단 거리를 검색할 때, 최단 경로를 갱신할 때마다 이중 리스트에 부모노드를 저장해둡니다.

그리고 dfs를 이용해 간선을 제거한 뒤, 다시 다익스트라를 이용해 거의 최단 경로를 구합니다.

재채점되면서 시간 초과가 떴습니다.

어느 부분에서 최적화가 덜된 걸까요?

import java.io.*;
import java.util.*;

/*
거의 최단 경로
https://www.acmicpc.net/problem/5719
 */
public class Main {
	static int n,m;
	static int start, dest;
	static int[][] roads;
	static int[] dist;
	static List<List<Node>> parents; 
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		StringBuilder sb = new StringBuilder();
		while(true) {
			String line = reader.readLine();
			if(line.equals("0 0")) break;
			StringTokenizer st = new StringTokenizer(line);

			n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
			parents = new ArrayList<>();
			for (int i = 0; i < n; i++) parents.add(new ArrayList<>());

			st = new StringTokenizer(reader.readLine());
			start = Integer.parseInt(st.nextToken()); 
            dest = Integer.parseInt(st.nextToken());

			roads = new int[n][n];
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(reader.readLine());

				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				int cost = Integer.parseInt(st.nextToken());
				roads[u][v] = cost;
			}
			//최단 경로 탐색
			dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE);
			diijkstra(start, true);
			//최단 경로 삭제
			deleteShortestPath(dest);
			//거의 최단 경로 탐색
			dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE);
			diijkstra(start, false);

			int ret = dist[dest];
			if(ret == Integer.MAX_VALUE) sb.append(-1+"\n");
			else sb.append(ret+"\n");
		}
		sb.deleteCharAt(sb.length()-1);
		System.out.println(sb.toString());
	}

	private static void deleteShortestPath(int here) {
		if(here == start) return ;
		
		for (int i = 0; i < parents.get(here).size(); i++) {
			Node parent = parents.get(here).get(i);
			roads[parent.id][here] = 0;
			deleteShortestPath(parent.id);
		}
	}

	public static void diijkstra(int start, boolean saveParent){
		PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparing(node -> node.cost));
		q.add(new Node(start,0));
		dist[start] = 0;

		while(!q.isEmpty()) {
			Node here = q.poll();
			if(here.cost > dist[here.id]) continue;

			for (int there = 0; there < n; there++) {
				if(roads[here.id][there] > 0) {
					int nextCost = here.cost + roads[here.id][there];

					if(nextCost < dist[there]) {
						// 더 짧은 경로를 발견하면 부모 리스트 초기화하고 다시 저장
						if(saveParent) {
							parents.set(there, new ArrayList<>());
							parents.get(there).add(here);
						}
						q.add(new Node(there, nextCost));
						dist[there] = nextCost;
					}
					//같은 간선인 부모 저장
					if(saveParent && nextCost == dist[there]) 
                        parents.get(there).add(here);
				}
			} //while
		}
	}
}
class Node {
	int id, cost;
	public Node(int id, int cost) {
		this.id = id;
		this.cost = cost;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}

pl0892029 3년 전 1

영향이 있을지 모르겠지만 최적화할 여지가 있어보이는 것을 짧게 이야기하겠습니다.

다익스트라 알고리즘 시 우선순위큐를 이용해서 O(ElogV)로 바뀌는 것은 잘 아실 겁니다.

그런데 위의 소스는 roads가 간선 정보를 의미하는 것으로 보이는데, 행렬로 구현되어있기 때문에 E = N^2 이 됩니다.

문제에서 명시되는 E는 10^4 이고, N^2 은 25 * 10^4 이기 때문에 최대 25배의 성능차이가 날 수 있습니다.

행렬이 아닌, 간선 정보들만 들고 루프를 도는 방식으로 변경하시면 조금 더 성능적으로 유리할 것으로 생각됩니다.

다른 부분은, 어디를 더 고쳐야될지 잘 모르겠네요.

간선 정보들만 잘 추려서 같은 알고리즘으로 푼 C++ 소스가 통과했습니다.

아마도 위의 내용을 수정한다면 좋은 결과가 있지 않을까 조심스레 추측해봅니다.

chldntjr1211 3년 전 1

시간내주셔서 감사하단 말부터 드립니다.

문제는 지적해주신 부분도 분명히 최적화할 여지가 있는 부분이 맞았습니다.

위처럼 행렬로 구현할 경우 간선을 제거할 때 O(1)의 복잡도로 이득을 볼 수 있지만

이 문제에선 다익스트라를 두 번 돌려야 하기 때문에 지적해주신 부분을 고치는게 최적화에 도움이 될 수 있는 부분이라고 생각했습니다.

그런데 인접 리스트로 바꾸고 해도 시간초과가 뜨더라구요. (저는 자바만 판 사람이라 다른 언어는 모르겠네요)

결국 문제는 해결했습니다.

주요한 문제는 DFS로 간선을 삭제하는 부분이더라구요. 저 부분에서 최악의 경우 10000개의 재귀 호출이 일어나게 되는데

이 부분을 BFS로 바꿔주니 통과했습니다~

smjage522 2년 전 1

이미 해결하셨지만,, deleteShortestPath 메소드 부분에서 roads[parent.id][here] != 0 일 경우에만 재귀호출하도록 수정되면 불필요한 재귀호출을 줄일 수 있을것 같습니다.

chldntjr1211 2년 전 1

7달전의코드라기억이가물가물하지만,

님이 지적해주신게 정확한 답인 듯 하네요.

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

문제

문제

출처

ICPC

자바 시간 초과 질문이요

chldntjr1211 3년 전 0

pl0892029 3년 전 1

chldntjr1211 3년 전 1

smjage522 2년 전 1

chldntjr1211 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말