[Silver I] 효율적인 해킹 - 1325 (JAVA)

 

문제 요약

 

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

---

문제 분석

그냥 무작정 전체 BFS돌기.

단, "A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다."의 기준을 만족하기 위해

A B가 들어온 경우, 간선은 B -> A가 되도록 설정한다.

---

코드

package Week13;

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

public class BOJ_1325 {
    static int N, M, maxCnt;
    static List<List<Integer>> listMap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N개의 컴퓨터
        N = Integer.parseInt(st.nextToken());
        // 신뢰하는 관계의 개수
        M = Integer.parseInt(st.nextToken());
        listMap = new ArrayList<>();
        for(int i = 0; i <= N; i++){
            listMap.add(new ArrayList<>());
        }
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            // 신뢰하는 관계가 A B
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            listMap.get(B).add(A);
        }
        // 가장 많은 컴퓨터를 해킹했을때의 카운트
        maxCnt = 0;
        // 컴퓨터 번호별로 해킹가능한 컴퓨터 대수 저장
        int[] cntArray = new int[N+1];
        // 1번컴퓨터부터 N번컴퓨터까지 모두 bfs수행
        for(int computerNum = 1; computerNum <= N; computerNum++){
            int tempCnt = bfs(computerNum, new boolean[N+1]);
            maxCnt = Math.max(maxCnt, tempCnt);
            cntArray[computerNum] = tempCnt;
        }
        String result = "";
        for(int i = 1; i <= N; i++){
            if(maxCnt == cntArray[i]){
                result += i + " ";
            }
        }
        System.out.println(result.trim());
    }

    private static int bfs(int computerNum, boolean[] v) {
        int cnt = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(computerNum);
        v[computerNum] = true;
        while(!q.isEmpty()){
            int currComputerNum = q.poll();
            for(int nextComputerNum : listMap.get(currComputerNum)){
                if(v[nextComputerNum] == false){
                    v[nextComputerNum] = true;
                    q.add(nextComputerNum);
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

---

정리

새로 배운 내용

없음

개선할 점

시간초가 너무 타이트하다.

백준에서 시간제한이 5초라고 할 경우, 자바 11은 기본시간제한*2+1의 시간을 준다.(출처)

본 코드의 경우 10160ms ~ 10920ms를 왔다 갔다 하는 걸 보니, 서버 성능에 따라 편차가 약 1초를 왔다 갔다 하는 거 같다. 11초에 너무 타이트하게 들어갔기 때문에 이를 보완할 다른 방법을 찾아봐야 할 것 같다.

더 찾아볼만한 사항

없음

---