글 읽기 - dfs 시간초과입니다..

dhseo89 5년 전 0

dfs를 이용해서 1부터 연관된거 N까지 끝까지 검사 만약 중간에 발견되면 (3)

다시 3부터 N까지 검사해서 ++

이런식으로 구현했는데 무한루프 도는거같네요...

예제가 넘 적은데ㅜㅜ 제가 어디가 잘못됐는지 알수잇을까요??

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Hacking {

	static int N;
	static int M,result;
	static List<Integer> list = new ArrayList<>();
	static boolean trust[][];
	static int start;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		trust = new boolean[N+1][N+1];
		for (int i = 0; i < M; i++) {
			//two는 one을 해킹
			int two = sc.nextInt();
			int one = sc.nextInt();
//			System.out.println(two+" "+one);
			trust[one][two] = true;
		}
		
		for (int i = 1; i <= N; i++) {
			//한개씩 돌면서 result++;
			result=0;
			result++;
			start = i;
			dfs(i,1);
		}
		Collections.sort(list);
		for (int i = 0; i < list.size(); i++) {
			if(list.get(0) == list.get(i)) {
				System.out.print((i+1)+" ");
			}
			else {
				return;
			}
		}
	}
	
	//해킹관계를 파악
	private static void dfs(int i, int hacking) {
		if(hacking == N+1) {
			if(i == start) {
			list.add(result); //0번째부터 들어감
			}
			return;
		}
//		System.out.println(i+" "+hacking+" "+result);
		if(trust[i][hacking]) {
			result++;
			dfs(hacking,1);
		}
		dfs(i,hacking+1);
	}
}

ppp7700 4년 전 0

혹시 자바 11로 제출해 보시겠어요?? 저도 똑같은 소스 자바로 제출하면 시간초과 자바11로 제출하면 맞았어요

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

문제

문제

출처

ICPC

dfs 시간초과입니다..

dhseo89 5년 전 0

ppp7700 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말