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

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

1325번: 효율적인 해킹

풀이

BFS 또는 DFS로 푸는 그래프 탐색 문제다.

모든 노드에 대해서 각 노드를 시작점으로 하는 BFS를 수행하여 연결된 노드의 수를 구하고, 그 수가 최댓값인 경우의 노드 번호를 구하면 된다.

이 때 주의할 점은 "A가 B를 신뢰한다"면 B -> A 방향으로 연결되는 간선을 추가해야 한다.

 

코드 (시간초과)

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

public class Main {
	
	static ArrayList<Integer> answer = new ArrayList<>();
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static int max = 0;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int n = Integer.parseInt(st.nextToken());
    	int m = Integer.parseInt(st.nextToken());
    	
    	for (int i = 0; i <= n; i++)
    		graph.add(new ArrayList<>());
    	
    	while (m-- > 0) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	graph.get(b).add(a);
    	}
    	
    	for (int i = 1; i <= n; i++) {
    		bfs(i, n);
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	for (int v: answer) {
    		sb.append(v + " ");
    	}
    	System.out.print(sb);
    }
    
    public static void bfs(int start, int n) {
    	int cnt = 1;
    	Queue<Integer> q = new LinkedList<>();
    	boolean[] visited = new boolean[n+1];
    	
    	q.add(start);
    	visited[start] = true;
    	
    	while(!q.isEmpty()) {
    		int cur = q.poll();
    		
    		for (int next: graph.get(cur)) {
    			if (!visited[next]) {
    				q.add(next);
    				visited[next] = true;
    				cnt++;
    			}
    		}
    	}
    	
    	if (cnt == max)
    		answer.add(start);
    	else if (cnt > max) {
    		max = cnt;
    		answer.clear();
    		answer.add(start);
    	}
    }
}

가장 많은 노드와 연결되어 있는 노드 번호를 저장하기 위해 ArrayList(answer)를 사용하였다.

BFS를 수행하여 연결된 노드의 수를 구할 때, 최댓값 max보다 더 큰 값을 구했을 경우 arrayList를 초기화하기 위해 clear() 메서드를 사용하였지만, arrayList.clear()의 시간복잡도는 O(n)이므로 최악의 경우 시간복잡도가 O(n^2)이 되므로 시간초과가 발생하였다.

 

정답 코드

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

public class Main {
	
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static int max = 0;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int n = Integer.parseInt(st.nextToken());
    	int m = Integer.parseInt(st.nextToken());
    	
    	for (int i = 0; i <= n; i++)
    		graph.add(new ArrayList<>());
    	
    	while (m-- > 0) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	graph.get(b).add(a);
    	}
    	
    	int[] result = new int[n+1];
    	for (int i = 1; i <= n; i++) {
    		result[i] = bfs(i, n);
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	for (int i = 1; i <= n; i++) {
    		if (result[i] == max)
    			sb.append(i + " ");
    	}
    	System.out.print(sb);
    }
    
    public static int bfs(int start, int n) {
    	int cnt = 1;
    	Queue<Integer> q = new LinkedList<>();
    	boolean[] visited = new boolean[n+1];
    	
    	q.add(start);
    	visited[start] = true;
    	
    	while(!q.isEmpty()) {
    		int cur = q.poll();
    		
    		for (int next: graph.get(cur)) {
    			if (!visited[next]) {
    				q.add(next);
    				visited[next] = true;
    				cnt++;
    			}
    		}
    	}
    	
    	max = Math.max(max, cnt);
    	return cnt;
    }
}

시간 초과가 나는 문제를 해결하기 위해, result 배열에 각 노드를 시작점으로 하는 연결된 노드의 수를 저장하였고 BFS를 수행할 때마다 최댓값 max를 업데이트하였다.

이 후 결과를 출력할 때 result[i] == max 인 경우에 노드 번호를 출력하도록 하였다.