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

🔺 문제

1325번: 효율적인 해킹

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static boolean visited[];       // 방문 배열
    static ArrayList<Integer>[] A;  // 인접 리스트
    static int answer[];            // 정답 배열
    
    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];
        answer = new int[N + 1];
        // 인접 리스트 채우기
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }        
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            
            A[S].add(E);
        }
    
        // 🔔 모든 노드에 대해 BFS 수행 🔔
        for(int i = 1 ; i <= N ; i++) {
            visited = new boolean[N + 1];
            BFS(i);
        }
        
        int maxVal = 0;
        for(int i = 1 ; i <= N ; i++) {
            maxVal = Math.max(maxVal, answer[i]);
        }
        
        for(int i = 1 ; i <= N ; i++) {
            if(answer[i] == maxVal) {
                System.out.print(i + " ");
            }
        }
    }
    
    public static void BFS(int node) {
        visited[node] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        
        while(!queue.isEmpty()) {
            int now_node = queue.poll();
            
            for(int i : A[now_node]) {
                if(!visited[i]) {
                    visited[i] = true;
                    answer[i]++;        // 신규 노드 인덱스의 정답 배열 값 증가시킴
                    queue.add(i);
                }
            }            
        }
    }
}

✅ 해결 아이디어
✔ BFS (단방향. 인접 리스트 사용)

 

💥 유의사항

⇨ 필요한 것

1) 인접 리스트

2) 정답 배열 (int형)

3) 방문 여부 배열 (boolean형)

 

 

---

🔺 다른 풀이들

- 복습용!

[알고리즘-PS] 백준 1325번 효율적인 해킹 자바 문제풀이 (시간 초과 해결)

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

 

---

💬 느낀 점

바로 BFS를 생각하긴 했다만

구현은 아직 완벽하지 못 함.

 

 

1회독	2회독	3회독	4회독	5회독
V	6/21

 

(+6/21 2회독)

정답 배열 만들기 & 모든 정점에 대해 bfs 수행

이걸 놓쳤다!

 

모든 정점에 대해 bfs 수행하는 아이디어를 자주 생각해내지 못 하는 것 같다..ㅠ

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static ArrayList<Integer>[] A;  // 인접 리스트
    static boolean[] visited;       // 방문 배열
    static int[] answer;            // 🔔 신뢰도 배열 🔔
    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(), " ");
        
        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<>();
        }
        
        visited = new boolean[N + 1];
        answer = new int[N + 1];
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            A[s].add(e);
        }
        
        // 🔔 모든 노드에 대해 bfs 수행 🔔 
        for(int i = 1 ; i <= N ; i++) {
            visited = new boolean[N + 1];
            bfs(i);
        }
        
        // 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1 ; i <= N ; i++) {
            if(answer[i] == max) {
                sb.append(i).append(" ");
            }
        }
 
        System.out.println(sb);
    }
    
    static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        
        visited[num] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    visited[next] = true;
                    answer[next]++; // 신뢰도 배열 값 업데이트
                    queue.add(next);
                    max = Math.max(max, answer[next]); // 최대값 탐색
                }
            }
        }
    }
}