[DFS] 백준 - 17220번: 마약수사대 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

17220번: 마약수사대

 

 

문제는 다음과 같다.

마약 공급책 헤더가 여러 사람에게 마약을 뿌리면 그 사람들도 밑으로 계속 공급하게 되고,

만약 공급책이 잡히게 되면 그 밑에 사람들은 공급을 받을 수 없게 된다.

 

처음 예제를 보고 계속 풀었는데 틀렸다고만 하길래 질문하기에 보니

마약 공급책(헤더)이 한 명이 아닌 여러 명일 수 있다고 하였다.

 

그리고 거기서 제시해준 반례를 돌려도 답은 맞았으나 제출하니 틀리기만 하였다.

허허허..

그래서 반례를 만들어서 적용해 보니 문제점을 알았고 해결하였다.

(반례 만드는 것도 중요한 것 같다.. 이거로 시간 꽤 날렸다.)

6 4
A B
A C
C D
E F
2 C F

답: 1

 

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer>[] map;
    static boolean[] check;
    static int n;
    static int count;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();

        map = new ArrayList[n];
        check = new boolean[n];
        count = 0;

        int[] tempHeader = new int[n];
        List<Integer> header = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            map[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int a = String.valueOf(sc.next()).charAt(0) - 'A';
            int b = String.valueOf(sc.next()).charAt(0) - 'A';
            map[a].add(b);
            tempHeader[b]++;
        }

        for (int i = 0; i < tempHeader.length; i++) {
            if (tempHeader[i] == 0) {
                header.add(i);
            }
        }

        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a = String.valueOf(sc.next()).charAt(0) - 'A';

            map[a].clear();
            if (!header.contains(a)) {
                for (int j = 0; j < map.length; j++) {
                    map[j].remove(Integer.valueOf(a));
                }
            }
        }

        for (int i = 0; i < tempHeader.length; i++) {
            if (tempHeader[i] == 0) {
                dfs(i);
            }
        }

        System.out.println(count);
    }

    private static void dfs(int start) {
        check[start] = true;

        for (int i = 0; i < map[start].size(); i++) {
            if (!check[map[start].get(i)]) {
                dfs(map[start].get(i));
                count++;
            }
        }
    }
}

 

나는 2차원 배열을 통해 알파벳을 숫자로 바꿨다.(A-0, B-1...)

그 후 마약 공급책(헤더)을 누구인지 구하고 삭제되는 노드들은 clear를 시켜주고, 그것과 연관되어 있는 노드 배열들에서도 삭제를 시켜주었다.

 

다음으로 아까 구한 헤더들을 통해 dfs를 돌려주면 끝이다.