효율적인 해킹

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

 

처음에는 아래와 같이 코드를 짜서 진행했는데 자꾸 시간 초과가 나서 질문 검색을 통해 어느정도 피드백을 받고 수정하였다.

 

import java.util.*;

public class Main {
	static int N, M;
	static boolean[] visited;
	static ArrayList<Integer>[] list;
	static int[] answer;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		N = scan.nextInt();
		M = scan.nextInt();
		visited = new boolean[N + 1];
		list = new ArrayList[N + 1];
		answer = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<Integer>();
			answer[i] = Integer.MIN_VALUE;
		}
		
		for (int i = 0; i < M; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			
			list[b].add(a);
		}

		for (int i = 1; i <= N; i++) {
			visited[i] = true;
			dfs(i, i, 1);
			visited[i] = false;
		}

		int max = Integer.MIN_VALUE;

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

	static void dfs(int now, int start, int cnt) {
		if(cnt > answer[start]) {
			answer[start] = cnt;
		}
		
		for (int i = 0; i < list[now].size(); i++) {
			if (visited[list[now].get(i)] == false) {
				visited[list[now].get(i)] = true;
				dfs(list[now].get(i), start, cnt+1);
				visited[list[now].get(i)] = false;
			}
		}
	}
}

 

아래는 수정한 코드인데 제출언어를 java로 할 경우 어쩔때는 되고 어쩔때는 안된다. java 11로 하면 성공적으로 '맞았습니다!' 메시지가 뜬다

 

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

public class Main {
	static int N, M;
	static boolean[] visited;	// 이미 탐색한 컴퓨터인지 여부
	static ArrayList<Integer>[] list;	// 컴퓨터간 인접리스트
	static int[] answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	// 메모리를 줄위기 위한 BufferedReader 사용
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		list = new ArrayList[N + 1];
		answer = new int[N + 1];

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

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			list[a].add(b);
		}

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

		int max = Integer.MIN_VALUE;

		for (int i = 1; i <= N; i++) {
			if (max < answer[i]) {
				max = answer[i];
			}
		}

		StringBuilder sb = new StringBuilder();	// 메모리 최적화를 위한 StringBuilder

		for (int i = 1; i <= N; i++) {
			if (max == answer[i]) {
				sb.append(i + " ");
			}
		}

		System.out.println(sb.toString());
	}

	static void dfs(int now) {
		visited[now] = true;

		for (int next : list[now]) {
			if (visited[next])
				continue;

			answer[next]++;	// now->next 일때 next와 같이 해킹 될 수 있는 컴퓨터 수 증가
			dfs(next);

		}
	}
}

 

문제출처

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