글 읽기 - 동굴 탐색 시간 초과 문의

yoodly 5년 전 0

안녕하세요.

얼마 전에 JAVA 재채점으로 시간 초과가 발생했는데, BufferedReader, BufferedWriter로 IO를 개선해 봐도 똑같이 시간초과가 발생합니다.

위상정렬을 사용해서 O(N)으로 풀어서 로직으로는 시간을 더 줄일 수 없는 것 같은데, 12% 인근에서 시간 초과가 계속 발생하네요.

입력 테스트 케이스가 뭐길래 그런지.. ㅠㅠ

조언 부탁드립니다~

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

class Cave {
	public int arrival;
	public int cost;
	
	Cave (int arrival, int cost) {
		this.arrival = arrival;
		this.cost = cost;
	}
}

public class Main {
	static StringBuffer caveorder;
	static int cavecnt;
	static BufferedWriter bw;
	
	public static void main(String[] args) throws Exception {
		int T, N, E, from, to, cost;
		int[] value, degree;
		ArrayList<ArrayList<Cave>> ar = new ArrayList<ArrayList<Cave>>();
		ArrayList<Cave> caves;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			value = new int[N+1]; degree = new int[N+1];
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) value[i+1] = Integer.parseInt(st.nextToken());
			
			for (int i = 0; i <= N; i++) ar.add(i, new ArrayList<Cave>());
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				from = Integer.parseInt(st.nextToken());
				to = Integer.parseInt(st.nextToken());
				cost = Integer.parseInt(st.nextToken());
				caves = ar.get(from);
				caves.add(new Cave(to, cost));
				ar.set(from, caves);
				degree[to]++;
			}
			sort(ar, degree, value);
		}
		bw.close();
	}
	
	static void sort(ArrayList<ArrayList<Cave>> ar, int[] degree, int[] value) throws Exception {
		int from, to, cost, maxvalue, lastcave, idx;
		int size = degree.length - 1;
		int[] sequence = new int[size + 1];
		int[] valuesum = new int[size + 1];
		
		Cave cave;
		ArrayList<Cave> caves = new ArrayList<Cave>();
		LinkedList<Integer> que = new LinkedList<Integer>();
		
		lastcave = 1;
		Arrays.fill(valuesum, -10000); // 비용은 최대인데 보물의 가치가 0일 수 있으므로, 가장 낮은 가치로 초기화
		maxvalue = valuesum[1] = value[1];
		que.add(1);
		
		for (int i = 1; i <= size; i++) {
			if (que.isEmpty()) return;
			from = que.poll();
			caves = ar.get(from);
			for (int j = 0; j < caves.size(); j++) {
				cave = caves.get(j);
				to = cave.arrival;
				cost = cave.cost;
				// 기존 수익보다 새로 동굴을 파는 수익이 큰 경우 업데이트하고, 동일할 경우 경로만 추가
				if (valuesum[to] < valuesum[from] + value[to] - cost) {
					valuesum[to] = valuesum[from] + value[to] - cost;
					if (maxvalue < valuesum[to]) {
						maxvalue = valuesum[to];
						lastcave = to;
					}
					sequence[to] = from;  // 최대 가치인 경우 어느 동굴에서 이동해 왔는지 기록
				}
				if (--degree[to] == 0) que.add(to);
			}
		}
		
		cavecnt = 1;
		caveorder = new StringBuffer();
		idx = lastcave;;
		while (idx > 1) {
			caveorder.insert(0, " "+idx);
			cavecnt++;
			idx = sequence[idx];
		}	
		caveorder.insert(0, "1");
		bw.append(maxvalue+" "+cavecnt+"\n");
		bw.append(caveorder.toString()+"\n");
		bw.flush();
	}
}

yoodly 5년 전 0

조언 감사드립니다.

StringBuffer를 사용하지 않고 BufferedWriter에 바로 추가를 했는데도 역시나 4%에서 진행하다가 time out이 나네요 ㅠ (위의 질문과 동일 위치)

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

class Cave {
	public int arrival;
	public int cost;
	
	Cave (int arrival, int cost) {
		this.arrival = arrival;
		this.cost = cost;
	}
}

public class Main {
	static int cavecnt;
	static BufferedWriter bw;
	
	public static void main(String[] args) throws Exception {
		int T, N, E, from, to, cost;
		int[] value, degree;
		ArrayList<ArrayList<Cave>> ar = new ArrayList<ArrayList<Cave>>();
		ArrayList<Cave> caves;

		System.setIn(new FileInputStream("E:\\workspace\\software_test\\src\\sample_data.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			value = new int[N+1]; degree = new int[N+1];
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) value[i+1] = Integer.parseInt(st.nextToken());
			
			for (int i = 0; i <= N; i++) ar.add(i, new ArrayList<Cave>());
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				from = Integer.parseInt(st.nextToken());
				to = Integer.parseInt(st.nextToken());
				cost = Integer.parseInt(st.nextToken());
				caves = ar.get(from);
				caves.add(new Cave(to, cost));
				ar.set(from, caves);
				degree[to]++;
			}
			sort(ar, degree, value);
		}
		bw.close();
	}
	
	static void sort(ArrayList<ArrayList<Cave>> ar, int[] degree, int[] value) throws Exception {
		int from, to, cost, maxvalue, lastcave, ridx, fidx;
		int size = degree.length - 1;
		int[] reverse = new int[size + 1];
		int[] forward = new int[size + 1];
		int[] valuesum = new int[size + 1];
		
		Cave cave;
		ArrayList<Cave> caves = new ArrayList<Cave>();
		LinkedList<Integer> que = new LinkedList<Integer>();
		
		lastcave = 1;
		Arrays.fill(valuesum, -10000); // 비용은 최대인데 보물의 가치가 0일 수 있으므로, 가장 낮은 가치로 초기화
		maxvalue = valuesum[1] = value[1];
		que.add(1);
		
		for (int i = 1; i <= size; i++) {
			if (que.isEmpty()) return;
			from = que.poll();
			caves = ar.get(from);
			for (int j = 0; j < caves.size(); j++) {
				cave = caves.get(j);
				to = cave.arrival;
				cost = cave.cost;
				// 기존 수익보다 새로 동굴을 파는 수익이 큰 경우 업데이트하고, 동일할 경우 경로만 추가
				if (valuesum[to] < valuesum[from] + value[to] - cost) {
					valuesum[to] = valuesum[from] + value[to] - cost;
					if (maxvalue < valuesum[to]) {
						maxvalue = valuesum[to];
						lastcave = to;
					}
					reverse[to] = from;  // 최대 가치인 경우 어느 동굴에서 이동해 왔는지 기록
				}
				if (--degree[to] == 0) que.add(to);
			}
		}
		
		cavecnt = 1;
		ridx = lastcave; fidx = 0;
		while (ridx > 1) {
			cavecnt++;
			forward[fidx++] = ridx;
			ridx = reverse[ridx];
		}	
		bw.append(maxvalue+" "+cavecnt+"\n");
		bw.append("1");
		for (int i = 0; i < fidx; i++) bw.append(" "+forward[fidx-i-1]);
		bw.newLine();
		bw.flush();
	}
}

djm03178 5년 전 1

그것과 거의 똑같은 이유로 시간이 오래 걸리는 것이 또 있습니다.

main 메서드에서 ar을 한 번만 만들어두고 이후에는 매 테스트 케이스마다 0~N까지의 인덱스에 새로운 ArrayList를 끼워넣는 식으로 구현하고 있는데 이러면 새 오브젝트를 추가할 때마다 기존에 그 인덱스 이후에 있던 모든 오브젝트들이 전부 한 칸씩 뒤로 밀려나야 합니다. 그래서 테케마다 누적될수록 더욱 많은 시간이 걸립니다.

매 테스트 케이스마다 ar = new ArrayList<ArrayList<Cave>>(); 를 새로 해주면 통과됩니다.

yoodly 5년 전 0

제가 테케 마다 객체를 생성하지 않고 맨 앞에서 한번만 객체를 생성한지 생각도 못헀지만, 그게 문제인지는 정말 꿈에도 생각하지 못했습니다.

해결할 때까지 보아주셔서 정말로 감사드립니다~ ^^

배열 형태의 자료구조에서 임의의 위치에 새로운 원소를 끼워넣는 메서드 자체를 사용하지 않는 것이 좋습니다. ArrayList의 경우 add 메서드의 첫 번째 인자로 인덱스를 넘겨줘야 할 일은 거의 없습니다. 배열의 형태라면 맨 끝에 추가/삭제, 임의의 위치에 접근/수정만 사용하는 것이지 중간에 원소를 끼워넣거나 빼는 연산의 시간은 항상 뒤에 있는 원소들 전체에 영향을 받는다는 사실을 잊지 마세요.

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

문제

문제

출처

ICPC

동굴 탐색 시간 초과 문의

yoodly 5년 전 0

djm03178 5년 전 1

yoodly 5년 전 0

djm03178 5년 전 1

yoodly 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말