글 읽기 - 11725번 시간초과 도대체 어떻게...

rlagustlr677 5년 전 1

bfs로 순번을 정해서 앞에껄 부모로 했습니다.. 시간초과가나요 ㅠㅠ

printf로도 해봤는데 시간초과가 나네요

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class test2 {
    
	static int N;
	
	static int V1;
	
	static int V2;
	
	static int im2[];
	
	static int check[];
	
	static Queue<Integer> q=new LinkedList<Integer>();
	
	static ArrayList<Integer>[] a; 
	
    public static void main(String args[]) {
        
        Scanner input=new Scanner(System.in);
        
        N=input.nextInt();       
 
        im2=new int[N+1];
        
        im2[0]=-1;
        
        a=(ArrayList<Integer>[])new ArrayList[N+1];
        
        check=new int[N+1];
        
        for(int i=1;i<=N;i++) {
        	
        	a[i]=new ArrayList<Integer>();
        	
        }
        
        for(int i=1;i<N;i++) {
        	
        	V1=input.nextInt();
        	
        	V2=input.nextInt();
        	
        	a[V1].add(V2);
        	
        	a[V2].add(V1);
        }
        
        input.close();
        
       bfs();
       
       for(int i=2;i<=N;i++) {
    	   
    	   System.out.println(im2[i]);
       }
    }
    
    static void bfs() {
    	
    	check[1]=1;
    	
    	q.add(1);
    	
    	int V;
    	
    	while(!q.isEmpty()) {
    		
    		V=q.remove();
    		
    		for(int i=1;i<=N;i++) {
    			
    			if(a[V].contains(i)&&check[i]==0) {
    				
    				check[i]=1;
    				
    				im2[i]=V;
    				
    				q.add(i);
    			}
    		}
	  		
    	}
    }
}

rlagustlr677 5년 전 0

2차원 배열로하면 아에 런타임에러가 나네요 크기가 너무커서 ㅠㅠ

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

문제

문제

출처

ICPC

11725번 시간초과 도대체 어떻게...

rlagustlr677 5년 전 1

rlagustlr677 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말