백준 : 1325 (효율적인 해킹) (DFS)

이번문제는 간단한 DFS로 풀수 있는 문제였습니다.

 

다만, 시간초과 이슈로 계속 틀려 찾아보고 여러가지 수정하여 정답이 맞았으나.. 

맞은 정답의 원인을 찾고자 다시 맞은답을 실행해 보니... 틀렸다는... 무슨일인가... 원인을 어떻게 찾으란 밀인가..

 

일단 내가 생각한 시간문제를 해결하는 방법을 적어보겠습니다.

1. Scanner 대신 BufferedReader, StringTokenizer 사용하기

2. public class Main 대신 class Main 사용하기

3. 불필요한 import문 제거

정도인것 같다. 

 

이문제의 핵심 역시 dfs를 각 노드별로 반복해서 수행한다는 점이다.

그리고 감염되는 컴퓨터수를 조건에 맞게 증가하면 끝!!!

 

보다 명확한 시간초과문제 해결방법이 나오게되면 참고해봐야겠다. 후후

 

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

class Main {

	static int n, m, max = 0;
	static boolean[] visited;
	static int[] dp = new int[n];
	static ArrayList<Integer>[] graph;

	public static void dfs(int now) {
		visited[now] = true; // 방문표시

		for (int i : graph[now]) {
			if (visited[i] == false) { // 아직방문전
				dp[i]++; // 감염수
				dfs(i); // 재귀
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		dp = new int[n];
		visited = new boolean[n];

		graph = new ArrayList[n + 1];
		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList();
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			graph[x - 1].add(y - 1);
		}

		for (int i = 0; i < n; i++) {
			visited = new boolean[n]; // 초기화
			dfs(i);
		}

		int max = 0;
		for (int i = 0; i < n; i++) {
			if (max < dp[i]) {
				max = dp[i];
			}
		}

		for (int i = 0; i < n; i++) {
			if (max == dp[i]) {
				System.out.print(i + 1 + " ");
			}
		}
	}
}