글 읽기 - 시간초과 문제가 어디서 발생하는지 모르겠습니다 도와주세요 ㅠㅠ

pelto 6년 전 0

dfs로 구현 하였는데 어디서 시간초과가 발생하는지 찾을 수 없었습니다. 고수님들 도와주세요 ㅠㅠ

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
	static int N, M;
	static ArrayList<Integer>[] m;
	static int[] prior;
	static int count;
	static boolean[] check;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		m = new ArrayList[N + 1];
		prior = new int[N + 1];
		check = new boolean[N + 1];
		for(int i = 0; i < N + 1; i++) {
			m[i] = new ArrayList<>();
		}
		for(int i = 0; i < M; i++) {
			int v = sc.nextInt();
			int u = sc.nextInt();
			m[u].add(v);
		}
		for(int i = 1; i < N + 1; i++) {
			count = 0;
			dfs(i);
			prior[i] = count;
		}	
		int max = 0;
		ArrayList<Integer> q = new ArrayList<>();
		for(int i = 1; i < N + 1; i++) {
			if(max < prior[i]) {
				q.clear();
				max = prior[i];
				q.add(i);
			}
			else if(max == prior[i]) {
				q.add(i);
			}
		}
		Collections.sort(q);
		for(int i = 0; i < q.size(); i ++) {
			System.out.print(q.get(i) + " ");
		}
	}
	public static void dfs(int start) {
		check[start] = true;
		for(int i = 0; i < m[start].size(); i++) {
			int next = m[start].get(i);
			count++;
			if(!check[next])
				dfs(next);
		}
		check[start] = false;
	}
}

djm03178 6년 전 1

https://www.acmicpc.net/proble...

pelto 6년 전 0

djm03178님 유익한 정보 제공해주셔서 정말 감사드립니다. 그런데 입출력 방식을 BufferedReader / BufferedWriter 로 수정하여도

똑같이 시간초과가 발생하는데 혹시 제가 발견하지 못한 로직 상 문제가 있는지 여쭤보고 싶습니다. 항상 좋은 글 달아주셔서 감사합니다.

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

문제

문제

출처

ICPC

시간초과 문제가 어디서 발생하는지 모르겠습니다 도와주세요 ㅠㅠ

pelto 6년 전 0

djm03178 6년 전 1

pelto 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말