글 읽기 - 1005번 25%에서 런타임 에러가 나네요...

ye0823 6년 전 0

방법을 바꿨는데도 오류가ㅠㅠ 무엇이 문제일까요 도와주세요ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static int[] maxTime; // 해당 건물 건설까지의 최대 건설 시간을 저장해놓을 배열
	public static int[] time; // 해당 건물의 건설 소요 시간을 저장해놓을 배열
	public static boolean[] startCheck; // 처음 건설할 수 있는 건물들을 체크할 배열
	public static int value = 0; // 출력할 값
	// 건설 순서를 저장해놓을 배열
	public static HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer, ArrayList<Integer>>();
	public static int w = 0; // 건설해야할 건물

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int sequence = 0; sequence < t; sequence++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());

			// 필요한 모든 배열과 변수 초기화
			value = 0;
			time = new int[n];
			maxTime = new int[n];
			startCheck = new boolean[n];
			st = new StringTokenizer(br.readLine());

			// 건물 건설 소요 시간 저장
			for (int i = 0; i < n; i++) {
				time[i] = Integer.parseInt(st.nextToken());
			}

			// 건설 순서 저장
			for (int i = 0; i < k; i++) {
				st = new StringTokenizer(br.readLine());
				int first = Integer.parseInt(st.nextToken());
				int second = Integer.parseInt(st.nextToken());
				startCheck[second - 1] = true; // 이전 건물이 있는 경우 체크
				ArrayList<Integer> tempList = hm.get(first);
				if (tempList == null) {
					tempList = new ArrayList<Integer>();
					tempList.add(second);
					hm.put(first, tempList);
				} else {
					tempList.add(second);
				}
			}
			w = Integer.parseInt(br.readLine());

			// 이전 건물이 없는 건물들로부터 건설 실행
			for (int i = 0; i < n; i++) {
				if (!startCheck[i]) {
					construct(i + 1, 0);
				}
			}
			System.out.println(value);
		}
	}

	public static void construct(int num, int constructTime) {
		constructTime += time[num - 1];

		// 건설시간이 해당 단계까지 누적 건설 시간보다 클 경우만 실행.
		if (constructTime > maxTime[num - 1]) {
			maxTime[num - 1] = constructTime;
		} else if (maxTime[num - 1] > constructTime) {
			return;
		}
		// 목표 건물까지 도달할 경우, value값에 반영
		if (num == w) {
			if (constructTime > value) {
				value = constructTime;
			}
			return;
		}
		ArrayList<Integer> tempList = hm.get(num);
		if (tempList == null) {
			return;
		}
		// 다음 차례의 건물들에 목표 건물이 있을 경우 목표 건물만 건설 시작. 아니면 다음 차례 건물들 모두 건설 시작
		if (tempList.contains(w)) {
			construct(w, constructTime);
			return;
		} else {
			for (int temp : tempList) {
				construct(temp, constructTime);
			}
		}
	}
}

baekjoon 6년 전 0

아마도 재귀 호출이 너무 깊어서 스택 오버플로우가 나는듯 합니다.

재귀를 비재귀로 바꿔보세요.

ye0823 6년 전 0

@baekjoon

더 공부해야겠군요... 답변 주셔서 감사합니다!

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

문제

문제

출처

ICPC

1005번 25%에서 런타임 에러가 나네요...

ye0823 6년 전 0

baekjoon 6년 전 0

ye0823 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말