글 읽기 - [Java] 어떻게 해야 시간초과를 줄일수 있을까요?....

mah 5년 전 0

계시판을 살펴보니 위상정렬로 풀어야 한다는거 같습니다.

아직 공부하기 전인데 공부를 하고나서 다시풀어야할지....

어디서 시간을 줄일수 있는지를 모르겠습니다 ㅠㅠ...

package SAMSUNG;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ1005 {
    private static int N, K;
    private static long ans;
    private static ArrayList[] list;
    private static int[] times;

    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int testN  = Integer.valueOf(st.nextToken());
        while(testN-->0){
            st = new StringTokenizer(br.readLine());
            N = Integer.valueOf(st.nextToken()); // 건물의 개수
            K = Integer.valueOf(st.nextToken()); // 건설규칙의 개수

            times = new int[N+1]; // 건물을 짖는데 걸리는 시간
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<=N; i++){
                times[i] = Integer.valueOf(st.nextToken());
            }

            list = new ArrayList[N+1]; // 각 건물을 짖는데 필요한 선행조건의 건물리스트

            for(int i=1; i<list.length; i++){
                list[i] = new ArrayList<Integer>();
            }

            for(int i=0; i<K; i++){
                st = new StringTokenizer(br.readLine());
                int col = Integer.valueOf(st.nextToken());
                int row = Integer.valueOf(st.nextToken());

                list[row].add(col);
            }


            int endN = Integer.valueOf(br.readLine());
            Queue<Node> q = new PriorityQueue<>();

            for(int i=0; i<list[endN].size(); i++){
                int num = Integer.valueOf(list[endN].get(i).toString());
                q.offer(new Node(num, times[num]+times[endN]));
            }

            ans = 0;

            boolean isFinshed = false;
            Queue<Node> nodes = new LinkedList<>();

            while(!isFinshed){
                for(int i=0; i<q.size(); i++){
                    Node now = q.poll();
                    if(list[now.idx].size()==0){
                        ans = Math.max(ans, now.tot);
                        isFinshed = true;
                        break;
                    }

                    for(int j=0; j<list[now.idx].size(); j++){
                        int num = Integer.valueOf(list[now.idx].get(j).toString());
                        nodes.offer(new Node(num, now.tot+times[num]));
                    }
                }

                while(!nodes.isEmpty() && !isFinshed){
                    q.offer(nodes.poll());
                }
            }
            sb.append(ans + "\n");
        }
        System.out.println(sb);
    }
}

class Node implements Comparable<Node>{
    int idx;
    long tot;

    Node(int idx, long val){
        this.idx = idx;
        this.tot = val;
    }

    public int compareTo(Node n){
       return this.tot < n.tot ? 1:-1;
    }
}

djm03178 5년 전 0

이런 형식의 문제는 푸는 방법이 상당히 정형화되어 있습니다. 말씀하신 대로 위상 정렬을 공부해보시면 비교적 간단하게 해결할 수 있는 문제인 것을 알 수 있습니다. 이 문제의 경우 구글에 검색만 해도 푸는 방법을 설명한 글이 넘쳐나니 공부하고 풀어보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

[Java] 어떻게 해야 시간초과를 줄일수 있을까요?....

mah 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말