글 읽기 - 시간 초과 이유

es_e2b 2년 전 0

노드 수를 입력 받고,

노드 수-1만큼 간선 입력받고,

간선은 방향없는 그래프로 만들고,

간선이 하나밖에 없는 노드는 부모 노드밖에 안이어져 있으니 리프노드니까, 리프노드 리스트에 등록하고,

리프노드에 등록된 노드를 반복하며

타 리프노드 까지의 총 가중치 값을 맥스와 비교하여 저장했습니다.

질문 게시판에 등록된 모든 반례를 통과했는데,

이대로 제출하면 처음부터 바로 시간 초과가 나옵니다.

해결 부탁드립니다...ㅜㅜ

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

public class Main {
	static ArrayList<ArrayList<int[]>> al = new ArrayList<>();
	static ArrayList<Integer> leaf=new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int read() throws Exception {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32)
            n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }
    public static void main(String[] args) throws Exception {
    	int N=read();
    	al.add(new ArrayList<>());
    	for(int i=0;i<N;i++)
    		al.add(new ArrayList<>());
    	for(int i=1;i<N;i++) {
    		int parent=read();
    		int child=read();
    		int cost=read();
    		al.get(parent).add(new int[] {child, cost});
    		al.get(child).add(new int[] {parent, cost});
    	}
    	for(int i=1;i<=N;i++) {
    		if(al.get(i).size()==1)
    			leaf.add(i);
    	}
    	ArrayDeque<int[]> q=new ArrayDeque<>();
    	int max=0;
    	for(int start:leaf) {
    		boolean[] visited=new boolean[N+1];
    		q.add(new int[] {start,0});
    		visited[start]=true;
    		while(!q.isEmpty()) {
    			int[] now=q.poll();
    			for(int[] target:al.get(now[0])) {
    				if(visited[target[0]])continue;
    				visited[target[0]]=true;
    				if(leaf.contains(target[0])) {
    					max=Math.max(now[1]+target[1], max);
    					continue;
    				}
    				q.push(new int[] {target[0],now[1]+target[1]});
    			}
    		}
    	}
    	sb.append(max);
        bw.append(sb);
        bw.flush();
        bw.close();
    }
}

protarie 2년 전 3

모든 리프 노드에서 전부 시작하면 시간초과입니다.

답이 될 수 있는 특정한 노드에서 시작할 수 있도록 알고리즘을 구성해야 합니다.

----

이미 알고 계신 내용: 트리의 지름을 얻기위한 경로는 어떤 2개의 리프 사이의 경로입니다.

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

문제

문제

출처

ICPC

시간 초과 이유

es_e2b 2년 전 0

protarie 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말