[Java] 백준 1325번 : 효율적인 해킹

문제

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

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

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

입력

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

출력

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

예제 입력 1

5 4
3 1
3 2
4 3
5 3

예제 출력 1

1 2

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, M;
	private static List<Integer> []list;
	private static int []num;
	private static boolean []visited;


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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		list=new ArrayList[N+1];
		for(int i=1;i<=N;i++) list[i]=new ArrayList<>();
		num=new int[N+1];
		
		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++) {	// bfs 이용시
			visited=new boolean[N+1];
			bfs(i);
		}
        
//        for(int i=1;i<=N;i++) {	// dfs 이용시(dfs를 돌기 전에 시작값에 대한 방문 설정을 먼저 해주어야 함)
//			visited=new boolean[N+1];
//			visited[i]=true;
//			dfs(i);
//		}
		int max=Integer.MIN_VALUE;
		int idx=-1;
		for(int i=1;i<=N;i++) max=Math.max(max, num[i]);	// 최댓값 탐색
		for(int i=0;i<num.length;i++) {	// 결과값 출력
			if(num[i]==max) System.out.print(i+" ");
		}
	}

	private static void bfs(int x) {
		Queue<Integer> queue=new LinkedList<>();
		queue.add(x);
		
		visited[x]=true;
		
		while(!queue.isEmpty()) {
			int q=queue.poll();
			
			for(int i=0;i<list[q].size();i++) {
				int get=list[q].get(i);
				
				if(!visited[get]) {
					visited[get]=true;
					num[get]++;
					queue.add(get);
				}
			}
		}
	}
    
    private static void dfs(int x) {
		if(list[x].size()==0) return;
		for(int i:list[x]) {
			if(!visited[i]) {
				visited[i]=true;
				num[i]++;
				dfs(i);
			}
		}
	}
}

1. 신뢰 관계에 있는 컴퓨터를 배열로 표현해줍니다.

2. 1번부터 N번까지 그래프 탐색을 통해 해킹 가능한 컴퓨터의 대수를 구해줍니다.

3. 해킹 가능한 컴퓨터의 최대 대수를 구하고, 해당 값과 일치하는 컴퓨터의 번호를 오름차순으로 출력합니다.

 

그래프 탐색 과정에서 bfs와 dfs 모두 사용 가능하지만, bfs를 사용했을 때에는 시간적으로 효율성이 좀 더 높았고, dfs를 사용했을 때에는 메모리 측면에서 효율성이 좀 더 높았습니다.