BOJ - 1325 ) 효율적인해킹

 

---

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

---

신뢰성이 존재하는 컴퓨터 관계에서 하나의 컴퓨터를선택해서 가장많이 해킹할 수 있는 

 

컴퓨터를 뽑는 문제이다. 문제는 단순하지만, N=10000에서 완전탐색을 고민하게되는데,

나도 DFS+DP로 접근하였었다.

 

바로 틀렸습니다! 가 나오길래 사이클이 있는 경우에서 DP의 값이 이상하게 갱신되는것을 알 수 있었다.

그렇다면, 

1 ) DP를 사용하지않고 모든 경우에수에대해서 DFS 수행하는것과

2 ) 사이클을 체크해가면서 DP를 수행하는것

 

두가지의 선택사항으로 바뀔수 있게된다. 당연히2번으로 접근하려했지만 아이디어가 생각이안나서

1번 + 최적화의 방식으로 진행하였는데 JAVA 8에서는 시간초과가나던 코드가 JAVA 11에서는 3초의 여유를 남기고

통과하였다 JAVA11 과 JAVA 8에서 어떠한 시간차이가 존재하는지 공부해야겠다.

---

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

public class Main {

	public static int m,n,ans,max;
	public static ArrayList<Integer> map[];
	public static boolean visit[];
	public static int dp[];
	public static void main(String[] args) throws Exception {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			StringBuilder sb = new StringBuilder();
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			map = new ArrayList[n];
			dp = new int[n];
			for(int i = 0 ; i < n ; i ++) {map[i] = new ArrayList<>();}
			for(int i = 0 ; i < m ; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken())-1;
				int b = Integer.parseInt(st.nextToken())-1;
				map[b].add(a);
			}
			
			for(int i = 0 ; i < n ; i ++) {
				visit = new boolean[n];
				ans =0;
				dfs(i);
				max = ans > max ? ans : max;
				dp[i]= ans;
			}
			for(int i = 0 ; i < n ; i++) {
				if(dp[i]==max) sb.append((i+1)+" ");
			}System.out.print(sb);
	}
	private static void dfs(int i) {
		visit[i] = true;
		int size = map[i].size();
		for(int j = 0 ; j < size ; j++) {
			int next = map[i].get(j);
			if(!visit[next]) {
				ans++;
				dfs(next);
			}
		}	
	}
}

---