글 읽기 - 1005번 -자바 시간 초과 관련 질문드립니다.

ts930904 6년 전 0

1005 번 문제푸는데 시간초과 때문에 막혀있습니다.

bfs 와 dp를 이용하여 도전해보았으나 시간초과에서 빠져나오질 못하고있습니다 ㅠㅠ

제 코드에서 시간을 단축시키는 방법이 있을까요?

아니면 접근방식을 완전히 바꿔야할까요...?

고수님들의 도움 부탁드립니다. ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	//DP및 큐 전역변수 선언
	static int[] dp;
	static Queue<Integer> queue;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		//테스트 케이스 설정
		int T = Integer.parseInt(br.readLine());

		for (int i = 0; i < T; i++) {
			
			// N:건물 수 입력
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			
			//DP 설정
			dp = new int[N + 1];
			int[] delay = new int[N + 1];
			
			//K:경로수 설정 
			int K = Integer.parseInt(st.nextToken());
			boolean[][] path = new boolean[K + 1][K + 1];
			
			//delay[j] :  j건물 공사시간 
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				delay[j] = Integer.parseInt(st.nextToken());
			}
			
			//path[p1][p2]  : p1->p2  경로로  이동 가능한지 유무
			for (int j = 1; j <= K; j++) {
				st = new StringTokenizer(br.readLine());
				int p1 = Integer.parseInt(st.nextToken());
				int p2 = Integer.parseInt(st.nextToken());
				path[p1][p2] = true;
			}

			//W : 목표 건물
			int W = Integer.parseInt(br.readLine());
			
			//최초 DP[1] 설정
			dp[1] = delay[1];
			
			//큐 선언
			queue = new LinkedList<Integer>();
			//큐 삽입 데이터 : 건물 번호
			queue.offer(1);

			//인자 1:건설 시간 , 2:도착지점 , 3:경로 배열
			minBuildTime(delay, W, path);
			
			//결과 값 삽입
			sb.append(dp[W] + "\n");
		}
		//결과값 출력
		System.out.println(sb);
	}
	
	//매개변수 1:건설 시간 , 2:도착지점 , 3:경로 배열
	static void minBuildTime(int[] delay, int win, boolean[][] path) {
		//큐 값이 비게 될때까지 반복
		while (!queue.isEmpty()) {
			// 현재 건물번호 반환
			int poll = queue.poll();
			
			// 두건물을 동시에 짓게 될때 걸리는 시간
			int waitingTime = 0;
		
			
			for (int i = 1; i < path.length; i++) {
				// 현재 건물번호 와 연결되어있고, 나중에 지어야 하는 건물번호를 큐에 삽입
				if (path[poll][i] == true) {
					queue.offer(i);
				}

				// 현재 건물을 짓기에 앞서, 먼저 건설해야 하는 건물번호들중 최대 건설 시간 구하기 
				if (path[i][poll] == true) {
					if (dp[i] > waitingTime) {
						waitingTime = dp[i];
					}
				}
			}
			
			//현재 건물을 건설하기까지 최적 건설시간 : 이전 최적시간 + 현재 건설시간 
			dp[poll] = waitingTime + delay[poll];
			
			//만약 목표 건설건물이 완성됬을시 break;
			if (poll == win) {
				break;
			}

		}
	}
}

djm03178 6년 전 0

규칙의 수가 아주 많은(N^2 가까이) 것이 아닌 이상, 인접 행렬을 만드는 건 비효율적입니다. false일 확률이 높은데도 불구하고 N개를 다 돌아야 하기 때문이죠. 케이스마다 N^2 + K 시간이 걸리는데, 인접 행렬 대신에 꼭 필요한 간선만 추가하는 방식으로 하면 N + V 시간으로 단축할 수 있습니다.

게다가 지금 코드에서 path는 할당이 잘못된 것 같습니다. K는 건물 짓는 규칙의 수일 뿐이고, path는 [N + 1][N + 1]이 되어야 합니다.

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

문제

문제

출처

ICPC

1005번 -자바 시간 초과 관련 질문드립니다.

ts930904 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말