오답노트 #1325 : 효율적인 해킹

풀이방법 및 문제점

2022.05.28

자바로 시간초과를 안 내기가 매우 매우 어려운 문제다.

난 최선을 다했다...따흐흑

다른 언어로 시도한 사람들은 나와 똑같은 알고리즘으로도 성공했다.

자바로 시도한 다른 사람들은 동일한 코드를 여러 번 제출했더니 한 번은 시간초과, 한 번은 통과가 된다고 한다ㅋㅋㅋㅋㅋㅋㅋㅋ굉장히 빡빡한가 보다.

시간을 줄일 기발한 알고리즘이 떠오르지 않는 한, C++ 또는 Python으로 나중에 도전하는 것이 낫겠다.

 

코드

Java(2022.05.28)

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

public class Main {
	
	static ArrayList<Integer>[] arr;	//신뢰관계 정보 저장용 ArrayList 배열
	static boolean[] visited;	//방문여부 저장용 배열
	static int[] answer;	//컴퓨터별 해킹할 수 있는 컴퓨터의 수

	static void dfs(int start, int cur) {
		if(visited[cur]) return;
		
		visited[cur] = true;
		answer[start]++;
		for(int i: arr[cur])dfs(start, i);
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//n과 m 읽어오기
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		//필요한 변수들 선언 및 초기화
		arr = new ArrayList[n+1];
		for(int i = 1; i<n+1; i++) arr[i] = new ArrayList<Integer>();
		visited = new boolean[n+1];
		int max = -1;
		answer = new int[n+1];
		
		//신뢰관계를 읽어와 저장
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[b].add(a);
		}
		
		//깊이우선탐색 수행
		for(int i = 1; i<n+1; i++) {
			Arrays.fill(visited,false);
			dfs(i, i);
			max = Math.max(max, answer[i]);
		}
		
		//정답 출력
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i<n+1; i++) {
			if(answer[i] == max) sb.append(i + " ");
		}
		System.out.print(sb);
	}

}