• 백준 1325번 효율적인 해킹 :: 마이구미
    알고리즘 풀이/그래프 2018. 11. 21. 00:44
    반응형

    이 글은 백준 알고리즘 문제 1325번 "효율적인 해킹" 을 풀이한다.

    문제는 DFS 를 통해 접근한다.

    DFS 가 익숙하지 않는다면, 아래 관련 링크를 읽어보면 좋다.

    문제 링크 - https://www.acmicpc.net/problem/1325

    DFS - http://mygumi.tistory.com/102

    - 현재 코드(Java)는 최근 재채점으로 인해 시간초과를 발생시킨다


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

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

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


    A가 B 를 신뢰하는 경우에는 B 를 해킹하면, A 도 해킹할 수 있는...... 그러한 연결되어있는....

    연결되어있는 관계라면, 마치 바이러스처럼 퍼진다고 볼 수 있다.

    이러한 흐름은 양방향 그래프가 아닌 단방향 그래프를 연상시킬 수 있다.

    주어지는 입력에 대한 그래프는 다음과 같다. (여기서는 아직 방향을 나타내지는 않았다)


    1325번 효율적인 해킹

     

    결과적으로 DFS 또는 BFS 를 생각할 수 있다.

    쉽게 생각해서, 각 정점을 기준으로 연결된 간선을 통해 탐색하면 된다.


    오래전에 푼 문제였지만, 최근 데이터 추가로 인한 시간초과로 실패했다.

    우선 이전의 방식을 살펴본다.


    기본적인 BFS 를 통해 문제를 해결했었다.

    A->B 를 향하는 간선이 아닌, 반대로 B->A 로 접근한다.

    A가 B를 신뢰하는 관계에서 A를 해킹한다고 해서, B를 해킹할 수 있는게 아니기 때문이다.

    그래서 다시 그래프를 나타내면 다음과 같다.


    1325번 효율적인 해킹


    그 결과, 각 정점에 연결된 간선에 의한 정점들은 해킹할 수 있는 정점을 의미한다.

    각 정점을 기준으로 BFS 를 탐색하면 문제는 해결할 수 있고, 해결했었다.


    for (int i = 0; i < m; i++) { int v1 = sc.nextInt(); int v2 = sc.nextInt(); a[v2].add(v1); } for (int i = 1; i <= n; i++) { int cnt = 0; Arrays.fill(c, false); q.add(i); c[i] = true; while (!q.isEmpty()) { int v = q.poll(); for (int x : a[v]) { if (!c[x]) { q.add(x); c[x] = true; cnt++; } } }

    ........... }


    다시 풀이하는 과정에서, 계속해서 실패하는 BFS 방식으로 인해, 다른 방식인 DFS 로 접근했다.

    (본인이 작성한 BFS 방식인 실패한 이유는 마지막에 언급한다)


    이전 BFS 와는 다른 접근으로써, B->A 가 아닌 A->B 로 접근한다. 


    1325번 효율적인 해킹


    이 방식은 각 정점에 대해 재귀함수가 호출되는 횟수는 해킹할 수 있는 컴퓨터의 갯수와 동일하게 된다.

    이것이 의미하는 것은, DFS 를 통해 각 정점이 기준이 될 때, 탐색되어지는 정점은 현재 기준 정점을 해킹할 수 있다는 것을 의미한다.

    자세히 예를 들면, 다음과 같다.


    • 5번 정점을 기준으로 DFS 탐색하는 도중 3번 정점을 들렸다 => 3번 정점으로 인해 5번 정점은 해킹되어진다.
    • 5번 정점을 기준으로 DFS 탐색하는 도중 1번 정점을 들렸다 => 1번 정점으로 인해 5번 정점은 해킹되어진다.
    • 5번 정점을 기준으로 DFS 탐색하는 도중 2번 정점을 들렸다 => 2번 정점으로 인해 5번 정점은 해킹되어진다.


    위처럼 각 정점을 기준으로 DFS 를 통해 문제를 해결할 수 있다.


    이전 BFS 방식은 큐에서 삽입 및 삭제 연산을 통한 비용으로 인해, 시간초과를 초래한 것이 아닌가? 추측하고 있다.

    *다른 의견 및 알고 있는 것이 있다면 댓글을 부탁드린다.


    Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/1325.java


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    static ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[10001];
    static boolean[] visited = new boolean[10001];
    static int[] ans = new int[10001];
    static int cnt = 0;
     
    private void solve() {
        StringBuilder sb = new StringBuilder();
        int n = sc.nextInt();
        int m = sc.nextInt();
     
        for (int i = 1; i <= n; i++) {
            a[i] = new ArrayList<Integer>();
        }
     
        for (int i = 0; i < m; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
     
            a[v1].add(v2);
        }
     
        int max = 0;
        for (int i = 1; i <= n; i++) {
            visited = new boolean[10001];
            dfs(i);
        }
     
        for (int i = 1; i <= n; i++) {
            if (max < ans[i]) {
                max = ans[i];
            }
        }
     
        for (int i = 1; i <= n; i++) {
            if (max == ans[i]) {
                sb.append(i + " ");
            }
        }
     
        System.out.println(sb.toString());
    }
     
    public static void dfs(int v) {
        visited[v] = true;
     
        for (int vv : a[v]) {
            if (!visited[vv]) {
                ans[vv]++;
                dfs(vv);
            }
        }
    }
    cs


    반응형

    댓글 5

    • 토토토 2020.01.02 18:13

      문제를 보면 B가 A를 신뢰하는 경우 input이 A B라고 주어지는데 인접행렬 만들때 B->A사이에 간선이 있어야 하는거 아닌가요? 왜 A ->B 에 간선을 만드셨는지 궁금합니다.

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2020.01.08 17:22 신고

        일단 문제는 A가 B 를 신뢰하는 경우입니다.
        처음에 진행한 BFS 방식은 A 는 B 를 해킹할 수 없기에, B->A 간선을 두었습니다.

        DFS 방식은 일단 문제에서 요구한 것은 가장 많이 해킹할 수 있는 컴퓨터입니다.
        이 경우에는 B->A 간선을 두고 DFS 를 한다면, 탐색되어지는 정점은 해킹당하는 컴퓨터가 됩니다.
        하지만 문제에서 요구한 건 해킹할 수 있는 컴퓨터 이기 때문에 A->B 간선을 두고 진행하였습니다.

        그래서 언급한 부분은 다음과 같습니다.

        "DFS 를 통해 각 정점이 기준이 될 때, 탐색되어지는 정점은 현재 기준 정점을 해킹할 수 있다는 것을 의미한다."

    • Favicon of https://jellyinghead.tistory.com 스헤 2020.12.01 15:50 신고

      이 코드 시간초과나네요.

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2020.12.01 16:58 신고

        최근 재채점으로 인해, 다른 케이스가 추가된 것 같네요... 추후에 반영해보도록 하겠습니다.
        일단 시간초과라고 명시해둘게요 감사합니다~

    • 형광보라 2021.03.30 13:46

      입력 이해를 잘못하신 것 같습니다.
      그림이 잘못되었네요.
      입력 첫줄은 N 개의 vertex 와 M 개의 node (input) 이 있다는 것입니다.
      즉, 5 -> 4 에 대한 연결이 있다는 의미가 아닙니다.

Designed by Tistory.