링크

효율적인 해킹

문제

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

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

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

입력

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

출력

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

풀이

이 문제는 bfs 그래프 탐색을 통해 문제를 풀 수 있었다.
우선 각 노드들을 그래프 탐색을 통해 연결되어 있는 부분은 list에 저장
그 후 bfs를 통해 for에서 연결되어있는 부분들 중 아직 방문하지 않은 곳을 다시 queue에 집어넣어주며 카운트를 시켰다.

코드

package com.company.GraphSearch;

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

public class baek1325 {
    static class Edge{
        int x,y;
        Edge(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    static int N,M;
    static ArrayList<Integer>list[];
    static boolean[]visit;
    static int cnt[];
    static void input() 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());
        list=new ArrayList[N+1];
        cnt=new int[N+1];
        for(int i=1;i<=N;i++){
            list[i]=new ArrayList<>();
        }
        for(int i=0;i<M;i++){

            StringTokenizer st1=new StringTokenizer(br.readLine()," ");
            int x=Integer.parseInt(st1.nextToken());
            int y=Integer.parseInt(st1.nextToken());
            list[x].add(y);
        }
        for(int i=1;i<=N;i++){
                bfs(i);
        }
    }
    static void bfs(int x){
        visit=new boolean[N+1];
        visit[x]=true;
        Queue<Integer> q=new LinkedList<>();
        q.add(x);
        while(!q.isEmpty()){
            int temp=q.poll();
            for(int next:list[temp]){
                if(!visit[next]){
                    cnt[next]++;
                    visit[next]=true;
                    q.add(next);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        input();

        int max=0;
        for(int i=1;i<=N;i++) {
            if (max < cnt[i])
                max = cnt[i];
        }
        for(int i=1;i<=N;i++){
            if(max==cnt[i])
                System.out.print(i+" ");
        }
    }
}

아쉬웠던점

이 문제를 풀며 우선 A에서 B로 신뢰할경우 B->A로도 신뢰한다는 문장에서 처음 부터 바로 리스트에 양방향 모두 집어넣었었다.
하지만 이 문제 같은 경우 위처럼 초기화 시킬경우 각 리스트들이 전부 연결되어 버려 모두 최대값을 가져버렸다..
이 문제 하나로 몇시간을 잡아 먹었는지 모르겠다..