[BOJ] 백준 1325번 효율적인 해킹 (Java)

#1325 효율적인 해킹

난이도 : 실버 2

유형 : 그래프 / BFS

1325번: 효율적인 해킹

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

다른 정점으로 가장 많이 이어져있는 정점을 찾아주면 된다. BFS, DFS 어떤 것을 사용해도 상관없지만 해당 문제는 테스트케이스가 많이 빡빡하다.

 

BFS와 DFS의 시간복잡도는 O(V+E)로 같다. 그래서 어떤 것이 더 효율적이냐는 따질 수가 없고 개발자의 역량으로 문제의 유형에 따라 적합한 방식을 사용해야 한다. 해당 문제는 최단거리를 찾는 것이 아니고 1만 개의 정점들끼리의 관계를 탐색하는 것이므로 DFS로 푸는 것이 맞다고 생각했다. 그런데 DFS는 시간초과가 발생하고 BFS로 풀이하여야 통과하였다.

 

결과론적으로 다시 생각해보면 네트워크가 블록체인처럼 형성되어있다면 BFS가 더 효율적이라는 생각이 든다. 테스트케이스도 아마 아래 그림과 같은 관계를 지닌 샘플이 많을 것이다.

 

컴퓨터 신뢰 관계

 

풀이 코드 

풀이는 BFS탐색을 통해 각 노드에 연결되어 있는 노드의 수를 카운트해주어 가장 많은 노드와 연결되어있는 것을 출력해주면 된다. 시간복잡도는 모든 노드를 BFS 탐색해줘야하므로 O(N^2+NM)이다.

import java.io.*;
import java.util.*;

public class Main {

	static int n;
	static int[] rank;
	static List<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		rank = new int[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		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);
		}
		
		int max = Integer.MIN_VALUE;
		for(int i=1; i<n+1; i++) {
			bfs(i);
		}
		
		for(int i=1; i<n+1; i++) {
			max = Math.max(rank[i], max);
		}
		
		for(int i=1; i<n+1; i++) {
			if(max == rank[i]) {
				bw.write(i+" ");
			}
		}
		bw.flush();
		bw.close();
	}
	
	static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		boolean[] check = new boolean[n+1];
		q.add(start);
		check[start] = true;
		while(!q.isEmpty()) {
			int pos = q.poll();
			for(int next : list[pos]) {
				if(!check[next]) {
					check[next] = true;
					rank[next]++;
					q.add(next);
				}
			}
		}
	}
}