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

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

17220번: 마약수사대

 

문제

 

구현 알고리즘

해당 문제는 graph, dfs (또는 bfs)를 활용해서 푸는 문제 입니다. 해당 문제에서는 예외 케이스들이 존재해서 해결하는데 시간이 걸렸습니다.

 

확인사항

1. 마약 원산지는 제외하고 결과값을 구해야함

마약수사대가 소재지 파악에 원산지가 들어갈 수 있지만 최종적으로 구해야되는 값은 마약 공급자입니다.

그러므로 Root노드를 제외한 Edge노드만 counting해줘야합니다.

 

2. 마약 원산지는 무조건 'A'다?

마약원산지(Root)는 무조건 'A'가 아닙니다. B가 될 수도 있고 C가 될 수도 있습니다.

 

3. 마약 원산지는 한개다?

마약원산지(Root)는 한개가 아닐 가능성이 있습니다. 

 

이 3가지를 유의해서 문제를 풀어야합니다.

 

 

문제풀이

1. 마약 원산지(Root노드) 찾기

Root노드를 찾는 방법은 마약 공급책 관계 입력 부분에서 찾을 수 있습니다. 

 

예를 들면 입력 값 A B가 들어왔을 경우

A는 B의 마약 원산지, B는 마약 공급책입니다.

B는 마약 원산지가 될수 없는 것을 파악할 수 있습니다.

 

findRoot 배열에 마약공급책의 수 만큼 공간을 할당한 뒤, 입력받은 마약 공급책 관계(relation[1])의 마지막 값을 count 해줍니다.

ps. 저는 알파벳으로 되어있는 마약 공급책 구분자를 숫자로 변경했습니다. 결국 A -> 1, B-> 2 값으로 대체됩니다.

static int solution(BufferedReader reader) throws IOException {
    int[] findRoot = new int[numeric[0] + 1];
    
    for (int i = 0; i < numeric[1]; i++) {
        char[] relation = reader.readLine().replace(" ", "").toCharArray();
        graph.get(relation[0] - 64).add(relation[1] - 64);
        findRoot[relation[1] - 64]++;
    }
    
}

 

문제예제의 findRoot 결과값으로 아래 배열의 값이 나옵니다.

0 1 1 1 1 2 1 1 1 1 1

이를통해 배열의 첫번째가 마약원산지인 것을 알 수 있습니다.

 

2. 마약 수사대가 검거한 마약 공급자는 방문처리

입력받은 마지막 배열에 마약수사대가 검거한 마약 공급자들은 이제 운반할 수 없습니다. 그러므로 추후 dfs가 방문하지 않도록 방문처리를 해줍니다.

static int solution(BufferedReader reader) throws IOException {
	
    boolean[] visited = new boolean[numeric[0] + 1];
    
    // 생략 ...
    
	
    StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
    int n = Integer.parseInt(stringTokenizer.nextToken());

    for (int i = 0; i < n; i++) {
        int target = stringTokenizer.nextToken().toCharArray()[0] - 64;
        visited[target] = true;
    }
    
    // 생략 ...
}

 

3. 마약원산지를 기점으로 마약을 공급받을 수 있는 공급책 수 찾기

 

마지막으로 마약원산지(Root)에서 마약을 공급받을 수 있는 공급책들을 모두 찾습니다.  여기서 검거된 마약공급자(visited[start]=true)는 제외하고 카운트 해줍니다.

 

static int solution(BufferedReader reader) throws IOException {
	
    // 생략

	for (int i = 1; i < findRoot.length; i++) {
        if (findRoot[i] == 0) {
            dfs(i);
        }
    }
    
    // 생략
}

private static void dfs(int start) {
    if (!visited[start]) {
        List<Integer> targets = graph.get(start);
        for (Integer target : targets) {
            if (!visited[target]) {
                answer++;
                dfs(target);
            }
        }
    }

}

 

최종코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 마약수사대 (골드4)
 */
public class Main17220 {

    private static boolean[] visited;

    private static List<List<Integer>> graph;
    private static int answer;

    public static void main(String[] args) {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            System.out.print(solution(reader));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static int solution(BufferedReader reader) throws IOException {
        int[] numeric = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        answer = 0;
        graph = new ArrayList<>();
        visited = new boolean[numeric[0] + 1];
        int[] findRoot = new int[numeric[0] + 1];

        for (int i = 0; i <= numeric[0]; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < numeric[1]; i++) {
            char[] relation = reader.readLine().replace(" ", "").toCharArray();
            graph.get(relation[0] - 64).add(relation[1] - 64);
            findRoot[relation[1] - 64]++;
        }

        for (int i = 1; i < findRoot.length; i++) {
            System.out.print(findRoot[i] + " ");
        }

        StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());

        for (int i = 0; i < n; i++) {
            int target = stringTokenizer.nextToken().toCharArray()[0] - 64;
            visited[target] = true;
        }

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

        return answer;
    }

    private static void dfs(int start) {
        if (!visited[start]) {
            List<Integer> targets = graph.get(start);
            for (Integer target : targets) {
                if (!visited[target]) {
                    answer++;
                    dfs(target);
                }
            }
        }

    }


}