BOJ1325 효율적인 해킹 java

문제

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

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

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

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

어려운 겪은 포인트

[1]. 시간초과

N이 최대 10000이므로 2차원 배열에 map을 구성한 뒤, 풀이를 하게 되면 100001000010000이어서 시간초과가 발생

해결방법 : Map<Integer, List<Integer>>로 input을 받아서 시간 복잡도를 낮춰주었다.

 

[2]. map의 원소가 없을 때 break

처음에 queue에서 map.get(n)이 null일 때 break를 해줬는데 생각해보니 continue로 해줘야됐다.

해결방법 : break대신 continue로 변경

 

결국 1~N까지 모두 검사를 해줘야한다면 Map이 아닌 List<Integer>[] 형태로 짤 걸 그랬다.

import java.util.*;
import java.io.*;

public class Main {

    static int N, M;
    static Map<Integer, List<Integer>> map = new HashMap<>();
    static boolean[] visit;
    static int[] answers;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.valueOf(st.nextToken());
        M = Integer.valueOf(st.nextToken());
        answers = new int[N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.valueOf(st.nextToken());
            int B = Integer.valueOf(st.nextToken());
            map.putIfAbsent(A,new ArrayList<>());
            map.get(A).add(B);
        }

        for (int i = 1; i <= N; i++) {
            visit = new boolean[N + 1];
            visit[i] = true;
            bfs(i);
        }

        int max = Integer.MIN_VALUE;
        for (int computer : answers) {
            max = Math.max(computer,max);
        }
        for(int i = 1;i<=N;i++) {
            if(max == answers[i]) {
                sb.append(i + " ");
            }
        }

        System.out.println(sb.toString().trim());
    }

    private static void bfs(int first) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(first);
        while (!queue.isEmpty()) {
            int computer = queue.poll();
            visit[computer] = true;
            List<Integer> anotherComputers = map.get(computer);
            // if(anotherComputers == null) break; [실패원인코드]
			if(anotherComputers == null)continue;
            for (int anotherComputer : anotherComputers) {
                if (visit[anotherComputer]) continue;
                visit[anotherComputer] = true;
                queue.add(anotherComputer);
                answers[anotherComputer]++;
            }
        }
    }
}