이번에 풀어본 문제는
백준 1325번 효율적인 해킹 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N,M;
    static List<Integer> [] map;
    static boolean [] visited;
    static int [] total;
    static Queue<Integer> q;
    static int max_cnt = Integer.MIN_VALUE;
    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());

        map = new List[N+1];
        for(int i = 1; i <= N; ++i) map[i] = new ArrayList<>();
        for(int i = 0; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int fst = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());

            map[sec].add(fst);
        }

        total = new int[N+1];
        q = new LinkedList<>();
        for(int i = 1; i <= N; ++i)
        {
            if(!map[i].isEmpty())
            {
                visited = new boolean[N+1];
                visited[i] = true;
                q.add(i);
                while(!q.isEmpty())
                {
                    int cur = q.poll();
                    for(int n : map[cur])
                    {
                        if(!visited[n])
                        {
                            visited[n] = true;
                            total[i]++;
                            q.add(n);
                        }
                    }
                }
                max_cnt = Math.max(max_cnt,total[i]);
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 1; i <= N; ++i)
        {
            if(total[i] == max_cnt) bw.write(i+" ");
        }

        bw.flush();
        bw.close();
    }

}

📝 풀이

그래프 문제입니다.
어떤 컴퓨터를 해킹했을 때, 그 컴퓨터를 신뢰하고있는 다른 컴퓨터까지 같이 해킹할 수 있다고 합니다. 이러한 조건에서, 가장 많은 수의 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 구하는 문제입니다.
먼저 각 컴퓨터의 신뢰관계를 담기위한 List 배열을 만들어, a가 b를 신뢰한다면
List[b]에 a를 담아줍니다. 이렇게 입력값을 쭉 담아주게 되면, b를 해킹했을 때 연달아 해킹할 수 있는 a들을 알 수 있게 됩니다. 순서를 바꾸어도 상관 없겠지만, 저는 이쪽이 이해가 쉬운 것 같아 반대로 활용해 보았습니다.
입력 과정을 마치고, 저는 bfs를 사용했습니다. 시작값인 i를 큐에 담고, 큐 안에서는 i값과 연결된 컴퓨터들의 방문여부를 확인하며 너비탐색을 시작하게 됩니다. 도달할때마다 카운트를 누적해주고, 큐를 벗어난 후에는 가장 많은 수의 카운트를 구해야하기 때문에 max_cnt와 비교연산까지 해줍니다.
마지막으로 누적카운트가 담긴 total 배열을 순서대로 탐색하여 max_cnt와 같은 인덱스만을 버퍼에 담아준 후 출력해주면 해결됩니다.

📜 후기

시간초과 때문에 굉장히 애먹은 문제입니다. dfs를 사용해서 풀었는데 자꾸 시간초과가 나서, 그냥 혹시나 하는 마음으로 bfs를 사용해봤더니 통과되었습니다.
솔직히 큰 차이 없는거같은데 아직도 dfs코드가 왜 틀린지 이유는 잘 모르겠습니다 ㅋㅋㅋㅋㅋ
//시간초과 dfs 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static List<Integer> [] map;
    static boolean [] visited;
    static int [] total;
    static int max_cnt = Integer.MIN_VALUE;
    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());

        map = new List[N+1];
        for(int i = 1; i <= N; ++i) map[i] = new ArrayList<>();
        for(int i = 0; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int fst = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());

            map[sec].add(fst);
        }

        total = new int[N+1];
        for(int i = 1; i <= N; ++i)
        {
            if(!map[i].isEmpty())
            {
                visited = new boolean[N+1];
                visited[i] = true;
                dfs(i,i);
                max_cnt = Math.max(max_cnt,total[i]);
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 1; i <= N; ++i)
        {
            if(total[i] == max_cnt) bw.write(i+" ");
        }
        bw.flush();
        bw.close();
    }
    static void dfs(int i, int n)
    {
        for(int com : map[n])
        {
            if(!visited[com])
            {
                visited[com] = true;
                total[i]++;
                dfs(i,com);
            }
        }
    }
}