글 읽기 - 2%에서 시간초과 java 문의드립니다

mac475 4년 전 0

안녕하세요

2% 시간초과를 도저히 해결하지 못해 문의드려 봅니다

대략적 흐름은 다음과 같습니다

학생배열 순환하며 싸이클탐색 : 이때, 이미 팀배정완료된 학생은 탐색배제

탐색의 결과, 팀이 메이드 되었다면 그 시점의 멤버수 cnt를 dfs내에서 재귀적 반환

팀이 메이드되지 않았어도, n번재 학생에 대한 팀배정처리 내역은 완료됨, 이후 탐색배제

와 같습니다. 코드는 아래입니다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {	
	public static void main( String[] args ) throws Exception {
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int T = Integer.parseInt( br.readLine() );
		for( int i = 0; i< T; i++ ) {
			int n = Integer.parseInt( br.readLine() );
			String[] str_arr = br.readLine().split( " " );
			int[] graph = new int[n+1];																	// graph 배열선언
			for( int j = 1; j < n+1; j++ ) {														// graph 배열확보
				graph[j] = Integer.parseInt( str_arr[j-1] );
			}
			
			int sum = 0;
			boolean[] finished = new boolean[n+1];	// 순환시, 팀배정 완료학생의 경우 계산제외필요
			for( int V = 1; V < n+1; V++ ) {
				if( finished[V] == false && finished[graph[V]] == false ) {
					boolean[] visited = new boolean[n+1];										// 방문배열
					int cnt = 0;
					cnt = dfs( graph, visited, finished, V, V, cnt );	// dfs 시작
					if( cnt > 0 ) {																					// 팀made되면, 팀원을 확정지어 두어야 함
						// 방문했던 학생들이 팀원임
						for( int j = V; j < n+1; j++ ) {
							if( visited[j] == true )	finished[j] = true;
						}
					}
					sum += cnt;	
				}else {
				}
				finished[V] = true;
			}
			int output = n - sum;
			BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );
			bw.write( String.valueOf( output ));
			bw.flush();
			bw.close();
		}
	}
	public static int dfs( int[] graph, boolean[] visited, boolean[] finished, int V, int start, int cnt ) {
		visited[V] = true;											// 방문했음
		cnt++;
		int next_val = graph[V];
		boolean is_visited = visited[next_val]; 
		boolean is_finished = finished[next_val];
		if( next_val < start ) {
			cnt = 0;
			return cnt;
		}
		
		if( is_visited == false ) {
			if( is_finished == false )
				cnt = dfs( graph, visited, finished, next_val, start, cnt );
			else
				cnt = 0;
		}else {
			if( next_val != start ) {								// 팀이 made 실패함
				cnt = 0;
			}
		}
		return cnt;
	}
}

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

문제

문제

출처

ICPC

2%에서 시간초과 java 문의드립니다

mac475 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말