[백준_1325번] 효율적인 해킹

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

1325번: 효율적인 해킹

[문제]

 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

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

 

[입력 조건]

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

 

[코드]

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

public class BaekJoon_1325 {
	static int n;
	static int[] result;
	static ArrayList<Integer>[] map;
	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());
		
		map = new ArrayList[n+1];
		
		result=new int[n+1];
		for(int i=1;i<=n;i++) {
			map[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());
			
			map[a].add(b); // 단방향임을 주의!
		}
		
		// 각 컴퓨터마다 bfs 호출
		for(int i=1;i<=n;i++) 
			bfs(i);
		
		// 해킹할 수 있는 컴퓨터 개수의 최댓값 찾기
		int max=Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) 
			max=Math.max(result[i],max);
		
		// 최댓값을 갖는 검퓨터가 1대가 아닐 수 있으므로 모든 값 탐색
		for(int i=1;i<n+1;i++) {
			if(max==result[i]) {
				bw.write(i+" ");
			}
		}
		
		bw.flush();
		bw.close();
	}
	
	// DFS는 시간초과로 인해 bfs 사용
	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 now=q.poll();
			for(int next:map[now]) {
				if(!check[next]) {
					check[next]=true; // 방문처리
					result[next]++; // 해킹할 수 있는 컴퓨터 개수 count
					q.add(next);
				}
			}
		}
	}
}

 

[고찰]

 이번 문제는 난이도에 비해 정답률이 굉장히 낮은 문제였다. 문제를 풀어보니 자바를 사용했을 때 시간초과로 인해 계속 오답 처리를 받아 정답률이 왜이리 낮은지 깨달은 문제였다. 아무리 코드를 수정해봐도 시간초과 결과만 얻어 다른 사람의 코드를 참고했다.   

 이번 문제는 DFS 알고리즘을 사용하면 시간초과 판정이나 반드시 BFS 알고리즘을 사용해야 하는 문제이다. 그 이유는 정확히 몰라 답답하다. BFS를 사용하여 정답 처리를 받는 것은 쉬우나 왜 시간초과가 나는지 더 공부해야 하는 문제인것 같다.