1325번: 효율적인 해킹 [JAVA]_DFS, BFS

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

1325번: 효율적인 해킹

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

시간초과 진짜...ㅠ.ㅠ 될 때까지 했다 휴ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

🔔 시간 조금이라도 줄이기

1) 귀찮아서 import 문 작성할 때 그냥 *로 다 불러왔는데 따로 작성하는게 시간을 조금 줄일 수 있었다.

import java.util.*;   import java.io.*; → 필요한 것만 

2) Scanner → BufferedReader & StringTokenizer

System.out.println() → StringBuilder() 또는 BufferedWriter 

 

 

접근 방식)

B를 해킹하면, A를 해킹할 수 있는 것이기에 단방향으로만 노드 추가

result라는 신뢰도 배열 만들어서, DFS/BFS 돌면서 해킹할 수 있는 컴퓨터 수 추가해준다.

DFS/BFS 완료했으면, result 배열 돌면서, 가장 많은 컴퓨터 해킹할 수 있는 max 값 찾고 

해당 컴퓨터 번호 오름차순으로 출력

 

• DFS

package tony_git.graph_traversal;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class B_1325_DFS {
    static int N, M;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int[] result;

    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());
        A = new ArrayList[N + 1];
        result = new int[N + 1];

        for (int i = 1; i <= N; i++)
            A[i] = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
        }

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            DFS(i);
        }

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++)
            max = Math.max(max, result[i]);
        for (int i = 1; i <= N; i++) {
            if (result[i] == max)
                bw.write(i + " ");
        }
        bw.flush();
        bw.close();
    }

    static void DFS(int node) {
        visited[node] = true;
        for (int i : A[node]) {
            if (!visited[i]) {
                result[i]++;
                DFS(i);
            }
        }
    }
}

 

• BFS

package tony_git.graph_traversal;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_1325_BFS {
    static int N, M;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int[] result;

    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());
        A = new ArrayList[N + 1];
        result = new int[N + 1];

        for (int i = 1; i <= N; i++)
            A[i] = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
        }

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            BFS(i);
        }

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++)
            max = Math.max(max, result[i]);
        for (int i = 1; i <= N; i++) {
            if (max == result[i])
                bw.write(i + " ");
        }
        bw.flush();
        bw.close();
    }

    static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int i : A[now]) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    result[i]++;
                }
            }
        }
    }
}

 

 

+) 참고

https://hyeounstory.tistory.com/174

백준 : 1325 (효율적인 해킹) (DFS)

https://minhamina.tistory.com/111

[백준 - Java] 1325번 : 효율적인 해킹 (자바는 시간초과!!!!)