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

📖 문제

1325번: 효율적인 해킹

 

 

💡  풀이 방식

• BFS

. 입력값을 입력받아 어떤 컴퓨터에게 해킹 당할 수 있는지 담는다. (A[a].add(b))

. 각 노드마다 BFS를 수행해 노드별 해킹 컴퓨터 수를 저장한다.

 ⇒  a 노드를 탐색 시, a 노드가 아닌 a와 연결된 각 노드의 카운트를 올린다. (int형 카운트 배열 활용)

 

 

 

💥 유의사항

시간 초과 주의

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static List<Integer>[] A;
    static boolean[] visited;
    
    static int maxDepth = -1;
    static int[] cntArr; // 노드 별 해킹 컴퓨터 수 저장용 배열
    
    public static void main(String[] args) throws 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());
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++)   A[i] = new ArrayList<>();
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            A[a].add(b);
        }
        
        cntArr = new int[N + 1];
        
        for(int i = 1 ; i <= N ; i++) {
            visited = new boolean[N + 1];
            bfs(i);
        }
        
        for(int i = 1 ; i <= N ; i++) {
            if(cntArr[i] > maxDepth) {
                maxDepth = cntArr[i];
            }
        }
        
        for(int i = 1 ; i <= N ; i++) {
            if(maxDepth == cntArr[i]) {
                System.out.print(i + " ");
            }
        }
    }
    
    private static void bfs(int num) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(num);
        
        visited[num] = true;
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    q.add(next);
                    visited[next] = true;
                    cntArr[next]++;
                }
            }
        }
    }
}
 

 

 

➕ 다른 풀이 방식

- DFS 활용한 코드

[백준 - Java] 1325번 : 효율적인 해킹 (자바는 시간초과!!!!)

 

---

💦 어려웠던 점

- 분명 로직 다 맞게 작성했는데 시간 초과가 자꾸 떠서 환장하는 줄 알았다;;;🤯 Queue를 만들 때 LinkedList로 하면 시간초과가 떠서 ArrayDeque로 바꿨더니 맞았다. ㄴㅇㄱ

 

1회독	2회독	3회독	4회독	5회독
V	240617

---

(참고)

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

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