백준 1325(효율적인 해킹) JAVA

문제

1325번: 효율적인 해킹

노드의 갯수 n과 간선 정보 m이 주어집니다.

다음 줄에 간선 정보가 나오는데 예를 들어 3 4가 입력되면 4번 노드가 해킹되면 3번 노드도 해킹된다는 의미입니다.

그 중에서 하나의 컴퓨터를 해킹했을 때 컴퓨터가 최대로 해킹되는 컴퓨터 번호를 출력하면 됩니다.

만약 컴퓨터가 2개 이상이면 오름차순으로 출력합니다.

 

시간 초과가 매우 많이 났던 문제입니다.

처음에는 해당 간선 정보를 입력 받아 그래프 형태로 만들었습니다.

위의 예시로 보면 3 4 가 들어오면 

3  <--- 4 형태로 그래프를 구현하였습니다.

4번이 해킹되면 3번도 해킹된다는 의미였습니다.

즉, 예를 들어 list[4]={3, 2} 의 의미는 4번 컴퓨터를 해킹하면 3번, 2번 컴퓨터고 해킹할 수 있다는 것입니다.

하지만 이 경우 대부분 시간초과가 발생한다.

 

반대로 3 4가 들어오면 

3 ------> 4 형태로 그래프를 구현하면 어떤 컴퓨터를 해킹할 수 있는 지가 아니라, 어떤 컴퓨터에게 해킹 당할 수 있는지

확인하는 것이다.

list[3] = {1, 2} 의 의미는 3번 컴퓨터는 1, 2번 컴퓨터에 의해 해킹 당할 수 있다.

따라서 3번 노드를 탐색하더라도 1, 2번 노드의 카운트를 올리면 된다.

이것을 1 ~ n 번 노드를 시작점으로 계속 반복하면 된다.

for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
}

m개의 간선정보를 받아 list에 저장

for(int i=1;i<=n;i++){
      Arrays.fill(chk, false);
      //dfs(i);
      bfs(i);
}

1번 부터 n번 노드 까지 bfs 진행

static void bfs(int node){
        Queue<Integer>q = new LinkedList<>();
        q.add(node);
        chk[node] = true;
        while(!q.isEmpty()){
            int cur = q.peek();
            q.remove();
            for(int a : list[cur]){
                if(!chk[a]){
                    ans[a]++; /////포인트!!!!!
                    chk[a] = true;
                    q.add(a);
                }
            }
        }
    }

일반적인 bfs 이다.

포인트 부분에서 현재 node가 인접한 노드의 카운트를 늘려주는 것이다.

---

전체 코드입니다.

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

public class boj1325_효율적인해킹 {
    static ArrayList<Integer>[]list;
    static int[] ans;
    static boolean[] chk;
    static int hacking;
    static int maxHacking = -1;
    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());

        list = new ArrayList[n+1];
        for(int i=0;i<=n;i++)list[i] = new ArrayList<>();

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);

        }

        ans = new int[n+1];
        chk = new boolean[n+1];
        for(int i=1;i<=n;i++){
            Arrays.fill(chk, false);
            //dfs(i);
            bfs(i);
        }

        int max= 0;
        for(int i=1;i<=n;i++){
            max = Math.max(max, ans[i]);
        }

        StringBuffer sb = new StringBuffer();
        for(int i=1;i<=n;i++){
            if(max == ans[i]) sb.append(i + " ");
        }
        System.out.println(Arrays.toString(ans));
        System.out.println(sb.toString().trim());
    }
    static void dfs(int node){
        chk[node]=true;
        for(int nxt : list[node]){
            if(!chk[nxt]){
                ans[nxt]++;
                dfs(nxt);
            }
        }
    }
    static void bfs(int node){
        Queue<Integer>q = new LinkedList<>();
        q.add(node);
        chk[node] = true;
        while(!q.isEmpty()){
            int cur = q.peek();
            q.remove();
            for(int a : list[cur]){
                if(!chk[a]){
                    ans[a]++;
                    System.out.println(a);
                    chk[a] = true;
                    q.add(a);
                }
            }
        }
    }
}