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

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

1325번: 효율적인 해킹

* 문제가 살짝 이상한 것 같다. 정답이었던 코드도 다시 입력하면 시간 초과가 뜨기도 해서 운이 조금 필요하다.

 

* 풀이

기본적으로 ArrayList에 신뢰 관계를 입력하고, 각 노드 별로 이어진 노드들을 완전 탐색해서 가장 많은 컴퓨터가 이어진 노드들을 출력하면 된다.

 

* 첫번째 시도 - 신뢰 관계를 ArrayList에 입력할 때 a가 b를 신뢰할 경우 arr[b]에 a를 담았다. b를 해킹하면 a도 해킹할 수 있다는 뜻이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	static int N, M;
	static ArrayList <Integer>[] arr;
	static boolean isVisited[];
	static int max;
	static ArrayList result;
	static int cnt;
    
	static void BFS(int start) {
		Queue <Integer> que = new ArrayDeque<Integer>();
		
		que.add(start);
		isVisited[start] = true;
		
		while(!que.isEmpty()) {
			int now = que.poll();
			cnt++;
			for (int i : arr[now]) {
				if (isVisited[i]) continue;
				isVisited[i] = true;
				que.add(i);
			}
		}
	}
	

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		isVisited = new boolean[N+1];
		result = new ArrayList<Integer>();
		
		// 신뢰 관계 입력
		arr = new ArrayList[N+1];
		for (int i=0; i<N+1; i++) arr[i] = new ArrayList <Integer>();
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[b].add(a); // a가 b를 신뢰, b를 해킹하면 a도 해킹 가능
		}
		
		// 1번부터 N번까지 DFS
		for (int i=1; i<N+1; i++) {
			cnt = 0;
			isVisited = new boolean[N+1];
			//DFS(i);
			BFS(i);
			if (max < cnt) {
				max = cnt;
				result.clear();
				result.add(i);
			}
			else if (max == cnt) {
				result.add(i);
			}
		}
		
		for (int i=0; i<result.size(); i++) System.out.print(result.get(i)+ " ");
	}

}

하지만 위의 경우, 대부분 시간 초과가 떴다.

 

반대로 a가 b를 신뢰할 경우, arr[a]에 b를 담는다면 그 문제가 해결된다. 

어떤 컴퓨터를 해킹할 수 있는 지가 아니라, 어떤 컴퓨터에게 해킹 당할 수 있는 지 확인하는 것이다.

따라서 이어진 노드에 완전탐색을 하는 것은 동일하지만 a 노드를 탐색하더라도 a의 카운트를 올리는 것이 아닌 연결된 각 노드의 카운트를 올려야 한다.

 

* 코드

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

public class Main {
	static int N, M;
	static ArrayList <Integer>[] arr;
	static boolean isVisited[];
	static int max;
	static int cntArr[];
	
	static void DFS(int start) {
		isVisited[start] = true;
		for (int i : arr[start]) {
			if (isVisited[i]) continue;
			cntArr[i]++; // i가 해킹할 수 있는 숫자 증가
			DFS(i);
		}
	}
	
	static void BFS(int start) {
		Queue <Integer> que = new ArrayDeque<Integer>();
		
		que.add(start);
		isVisited[start] = true;
		
		while(!que.isEmpty()) {
			int now = que.poll();
			for (int i : arr[now]) {
				if (isVisited[i]) continue;
				cntArr[i]++; // i가 해킹할 수 있는 숫자 증가
				isVisited[i] = true;
				que.add(i);
			}
		}
	}
	

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		isVisited = new boolean[N+1];
		cntArr = new int[N+1];
		
		// 신뢰 관계 입력
		arr = new ArrayList[N+1];
		for (int i=0; i<N+1; i++) arr[i] = new ArrayList <Integer>();
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b); // a가 b를 신뢰, a는 b에게 해킹 당할 수 있음
		}
		
		// 1번부터 N번까지 search
		for (int i=1; i<N+1; i++) {
			isVisited = new boolean[N+1];
			//DFS(i); // 메모리↓ 시간↑
			BFS(i); // 메모리↑ 시간↓
			
		}
		
		// 해킹할 수 있는 최댓값 찾기
		for (int i=1; i<N+1; i++) {
			if (max<cntArr[i]) max = cntArr[i];
		}
		
		// 최댓값인 컴퓨터 출력
		for (int i=1; i<N+1; i++) if (max == cntArr[i]) System.out.print(i+" ");
	}

}

DFS와 BFS 모두 가능한데 DFS를 사용했을 때는 메모리를 적게 쓰지만 시간이 더 걸렸고, BFS를 사용했을 때는 메모리를 더 쓰지만 시간이 더 짧게 걸렸다.

 

첫번째 시도와 시간 복잡도 측면에서 다른 점을 모르겠지만 극단적인 케이스가 들어있어서 이런 결과가 나오는 게 아닌가 싶다.