글 읽기 - dfs로 풀었는데 왜 시간초과가 날까요?

amenable_c 1년 전 0

dfs로 풀었는데 시간초과가 납니다.
List를 배열로 사용하면 시간이 많이 걸려서 그런걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	static int N, M, cnt, max;
	static String[] s;
	static List<Integer>[] adj; 
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		s = br.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		
		adj = new ArrayList[N + 1];
		for(int i = 0; i <= N ;i++) {
			adj[i] = new ArrayList<>();
		}
		visited = new boolean[N + 1];
		for(int i = 0; i < M; i++) {
			s = br.readLine().split(" ");
		
			adj[Integer.parseInt(s[1])].add(Integer.parseInt(s[0]));
		}
		
		int[] ans = new int[N + 1];
		for(int i = 1; i <= N; i++) {
			if(adj[i].size() != 0) {
				Arrays.fill(visited, false);
				visited[i] = true;
				cnt = 0;
				dfs(i);
				
				ans[i] = cnt;
				max = Math.max(max, cnt);
				
			} else {
				ans[i] = 0;
			}
		}
		
		for(int i = 1; i <= N; i++) {
			if(ans[i] == max)
				sb.append(i).append(' ');
		}
		
		System.out.println(sb);
		
		
	}

	private static void dfs(int i) {
		
		for(Integer num : adj[i]) {
			if(!visited[num]) {
				visited[num] = true;
				cnt++;
				dfs(num);
			}
		}
	}
}

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

문제

문제

출처

ICPC

dfs로 풀었는데 왜 시간초과가 날까요?

amenable_c 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말