글 읽기 - 자바 DFS 시간초과 도움주실수 있는분?...

booting64 2년 전 0

시간 초과가 발생하는데 코드 어느부분을 고치면 될까요???

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

public class Main {
	static int V,ans;
	static boolean visit[];
	static ArrayList<Integer> adj[][];
    static FastReader scann = new FastReader();
    static StringBuilder sb = new StringBuilder();
  
	public static void main(String[] args) {
		V=scann.nextInt();
		adj=new ArrayList[V+1][2];
		visit=new boolean[V+1];
		for (int i = 1; i <= V; i++) {
			adj[i][0]=new ArrayList<>();
			adj[i][1]=new ArrayList<>();
		}
		for (int i = 1; i <= V; i++) {
			int c=scann.nextInt();
			while(true) {
				int a=scann.nextInt();
				if(a==-1) break;
				int b=scann.nextInt();
				adj[i][0].add(a);
				adj[i][1].add(b);
			}
		}
		
		pro();
	}

	private static void pro() {
		ans=Integer.MIN_VALUE;
		for (int i = 1; i <= V; i++) {
			System.out.println(adj[i][0].size());
			if(adj[i][0].size()==1)
				dfs(i,0);
		}
		sb.append(ans).append('\n');
		System.out.println(sb);
	}

	private static void dfs(int v,int cnt) {
		visit[v]=true;
		
		if(cnt>ans) ans=cnt;
		for (int i = 0; i < adj[v][0].size(); i++) {
			if(visit[adj[v][0].get(i)]==true) continue;	
			dfs(adj[v][0].get(i),cnt+adj[v][1].get(i));
		}
		visit[v]=false;
	}

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

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

문제

문제

출처

ICPC

자바 DFS 시간초과 도움주실수 있는분?...

booting64 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말