[BOJ] 1325-효율적인 해킹(Java) - BFS/시간초과

 

BFS로 풀이했다.

구현 자체는 어렵지 않았으나...4번이나 시간초과가 떴다

수정 내용은 다음과 같다.

수정 -> 시간초과를 반복하다 5번째에 통과했기 때문에 각 수정 내용이 얼만큼의 성능 개선을 이루었는지는 모르겠다

요점은 불필요한 반복은 최대한 제거했다는거(물론 더 제거할 여지가 있을수도 있다)

 

1. 큐 구현체 LinkedList → ArrayDeque 변경

• 아래는 Claude가 설명해준 내용임
• 캐시 효율 — 현대 CPU는 메모리를 캐시 라인 단위(보통 64바이트)로 읽어옵니다. ArrayDeque는 연속 메모리라 한 번 캐시에 올라오면 다음 요소도 이미 캐시에 있어요. LinkedList는 노드가 힙 곳곳에 흩어져 있어서 매번 캐시 미스가 발생합니다.
• GC 부담 — LinkedList는 노드 객체를 계속 생성/소멸하므로 GC가 더 자주 돌아요. BFS처럼 enqueue/dequeue가 수백만 번 일어나면 차이가 납니다.
• 시간복잡도는 동일 — offer/poll 모두 O(1)이라 Big-O로는 구분이 안 되고, 실제 상수 계수에서 차이가 납니다.
• 그럼 LinkedList는 언제 쓰나?
  • List 인터페이스도 동시에 필요할 때, 즉 중간 삽입/삭제를 인덱스로 자주 해야 할 때입니다. 순수하게 Queue/Deque로만 쓴다면 ArrayDeque가 항상 우선입니다. Java 공식 문서에도 Queue가 필요하면 LinkedList보다 ArrayDeque를 권장한다고 명시되어 있어요.

2. 정답 출력시 반복문에서 System.out.print 호출 →  StringBuilder 사용

 

3. 방문여부 체크용 visited 배열을 매 bfs마다 초기화 (new boolean[]) → 전역 변수로 뺴고 Arrays.fill(visited, false); 로 초기화

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static List<List<Integer>> list = new ArrayList<>();
	static boolean[] visited= new boolean[10001];
	static int[] arr;
	static int max;
	static int n;
	static int m;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n+1]; // i번 컴퓨터에서 시작해 해킹할 수 있는 컴퓨터 수
		max = 0;
		
		// 인접리스트 초기화
		for(int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
		}
		
		// 0. 다음 m개의 줄에 신뢰하는 관계 입력
		for(int i=0; i< m; i++) {
			st = new StringTokenizer(br.readLine());
			// a가 b를 신뢰한다 -> b를 해킹하면 a도 해킹할 수 있다
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list.get(b).add(a); // b를 해킹할 연달아 해킹할 수 있는 컴퓨터 리스트에 a를 넣는다
		}

		// 1. n개의 컴퓨터에 대해 반복문을 돌며 각 컴퓨터에서 해킹할 수 있는 컴퓨터 수를 arr에 저장
		for(int i=1; i<=n; i++) {
			Arrays.fill(visited, false);
			arr[i] = bfs(i);
		}
		
		// 2. 정답리스트를 오른차순 정렬 ->  정렬 없이 출력준비 동시에
		StringBuilder sb = new StringBuilder();
		List<Integer> answerList = new ArrayList<>();
		for(int i=1; i <=n; i++) {
			if(arr[i] == max) {
				answerList.add(i);
				sb.append(i).append(' ');
			}
		}
		
		// 출력
//		for(int k : answerList) {
//			sb.append(k).append(' ');
//		}
		System.out.println(sb.toString());
	}
	
	private static int bfs(int p) {
		int rv=1;
		
//		Queue<Integer> que = new LinkedList<>();
		Queue<Integer> que = new ArrayDeque<>();
		que.add(p);
		visited[p] = true;
		
		while(!que.isEmpty()) {
			
			int cur = que.poll();
			List<Integer> targetList = list.get(cur);
			for(int target : targetList) {
				if(!visited[target]) {
					que.add(target);
					visited[target] = true;
					rv++;
				}
			}
		}
		
		max = Math.max(max, rv);
		
		return rv;
	}
}