효율적인 해킹

in Algorithm on BeakJoon


백준 1325: 효율적인 해킹

문제보기
Alt text

풀이

시간제한이 타이트하여 Scanner를 사용하면 시간초과가 나기 때문에 BufferedReader 사용
주어진 신뢰 관계는 리스트배열에 담은 후 컴퓨터의 신뢰 관계를 dfs로 확인

  • dfs(int com, int start)
  • com : 현재 탐색하는 컴퓨터 번호
  • start : 처음 탐색을 시작한 컴퓨터 번호
  • visited : 방문체크

소스코드

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

public class Main {
	static ArrayList<Integer>[] lists;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer nm = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(nm.nextToken()); // 컴퓨터의 개수
		int M = Integer.parseInt(nm.nextToken()); // 신뢰 관계 수

		lists = new ArrayList[N + 1];
		for (int i = 0; i <= N; i++) {
			lists[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			StringTokenizer num = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(num.nextToken());
			int c = Integer.parseInt(num.nextToken());

			lists[c].add(r);
		}

		comCnt = new int[N + 1];
		for (int i = 1; i <= N; i++) {
				visited = new boolean[N + 1];
					dfs(i,i);
		}

		int max = 0;
		for (int i = 0; i < comCnt.length; i++) {
			if (max < comCnt[i])
				max = comCnt[i];
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < comCnt.length; i++) {
			if (max == comCnt[i])
				sb.append(i + " ");
		}
		System.out.println(sb.toString());

	}
	static int[] comCnt;
	static boolean[] visited;

	static void dfs(int com, int start) {
		comCnt[start]++;
		visited[com] = true;
			for (int i = 0; i < lists[com].size(); i++) {
				int n = lists[com].get(i);
				if(!visited[n])
					dfs(n,start);
			}
	}
}