[자바] 백준 1325번 효율적인 해킹

https://www.acmicpc.net/problem/1325

 

일단 이 문제는 단방향 그래프이기 때문에 한 쪽에만 갈 수 있는 정점에 대한 정보를 저장해야되는 게 특징이었다. 근데 나는 아직도 ArrayList 안에 배열 넣는 걸 선언하는 게 어렵다. 헷갈려요.., 무튼 입력 잘 받아주고 나서 처음에 dfs로 구현을 했는데.. 채점을 돌렸더니 1분동안 채점을 하는 엄청나게 시간이 오래 걸리는 코드를 구현해버렸다. 이와중에 dfs로 구현할 때 for문으로 구현하면 시간초과가 난다고 한다. dfs 구현 자체는 어렵지 않았다. 원래 알고 있는 dfs대로 잘 구현만 하면 됐고, 가장 많은 컴퓨터를 해킹하는 수를 미리 저장해두고 해당 값을 갖는 인덱스를 출력하는 방식으로 구현했다.

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

public class Main {
    static boolean[] visited;
    static ArrayList<Integer> count = new ArrayList<>();
    static int n, m;
    static ArrayList<Integer>[] graph;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n+1];
        for(int i = 0; i < n+1; i++){
            graph[i] = new ArrayList<>();
        }
        visited = new boolean[n+1];

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[b].add(a);
        }
        for(int i = 0; i < n; i++){
            dfs(i+1);
            count.add(cnt);
            visited = new boolean[n+1];
            cnt = 0;
        }
        int max_num = Collections.max(count); // ArrayList 중 가장 큰 수
        for(int i = 0; i < n; i++){
            if(max_num == count.get(i)){
                bw.write(String.valueOf((i+1))+ " ");
            }
        }
        bw.flush();
        bw.close();
    }
    public static void dfs(int x){
        visited[x] = true;
        for(int i: graph[x]){
            if(!visited[i]){
                cnt++;
                dfs(i);
            }
        }
    }
}

 

근데 시간 복잡도가 심상치 않으니 bfs로 다시 풀어봤다.

 

bfs로 풀어도 시간 복잡도가 그렇게 낮지 않은 것 같네 ..^^;

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

public class Main {
    static boolean[] visited;
    static ArrayList<Integer> count = new ArrayList<>();
    static int n, m;
    static ArrayList<Integer>[] graph;
    static Queue<Integer> queue = new LinkedList<>();
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n+1];
        for(int i = 0; i < n+1; i++){
            graph[i] = new ArrayList<>();
        }
        visited = new boolean[n+1];

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[b].add(a);
        }
        for(int i = 0; i < n; i++){
            bfs(i+1);
            count.add(cnt);
            visited = new boolean[n+1]; // 한 번 방문한 거 체크했으면 다음 접점에 대해 체크하기 위해 초기화
            cnt = 0;
        }
        int max_num = Collections.max(count); // ArrayList 중 가장 큰 수
        for(int i = 0; i < n; i++){
            if(max_num == count.get(i)){
                bw.write(String.valueOf((i+1))+ " ");
            }
        }
        bw.flush();
        bw.close();
    }
    public static void bfs(int x){
        queue.add(x);
        while(!queue.isEmpty()){
            int tmp = queue.poll();
            visited[tmp] = true;

            for(int i: graph[tmp]){
                if(!visited[i]){
                    visited[i] = true;
                    cnt++;
                    queue.add(i);
                }
            }
        }
    }