Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

1671. 상어의 저녁식사

(플레티넘 III) 이분 매칭 알고리즘을 이용하여 1671번 “상어의 저녁식사”를 풀어보았다.

문제 링크

풀이 알고리즘

  • 이분 매칭 (Bipartite Matching)
  • 깊이 우선 탐색 (Depth First Search)

풀이

이분 매칭 알고리즘을 응용하여 풀 수 있다.

각 상어를 하나의 정점으로 표현하면, 상어간의 먹이사슬 관계는 방향이 있는 간선으로 나타낼 수 있다.

이 때, 정점과 간선들로 만들 수 있는 트리의 최소 개수를 구하는 문제이다.

단, 문제에서 고려해야 할 두 가지 조건이 있다.

한 상어는 최대 두 마리의 상어만 먹을 수 있다.

각 정점마다 두 개의 정점을 매칭 시켜줘야 하므로, 정점마다 DFS를 2회 호출한다.

한 상어가 다른 상어를 잡아먹는 동안 나머지 상어들은 상어를 잡아먹을 수 없으며, 이미 잡아먹힌 상어는 다른 상어들을 잡아먹을 수 없다.

두 상어가 서로를 동시에 잡아먹을 수 없으므로, 서로 동일한 체급의 상어는 한쪽만 잡아먹힐 수 있도록 처리를 해준다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Stack;


class Shark {
    long size;
    long speed;
    long intelligence;

    boolean canEat(Shark prey) {
        return (this.size >= prey.size
                && this.speed >= prey.speed
                && this.intelligence >= prey.intelligence);
    }

    boolean isEqual(Shark shark) {
        return (this.size == shark.size
                && this.speed == shark.speed
                && this.intelligence == shark.intelligence);
    }
}


class Node {
    Node parentNode = null;
    Stack<Node> connectedNodes = new Stack<>();
    boolean isMatched = false;
}


public class Main {
    static final int MAX_NUMBER_OF_NODES = 50;
    static final int MATCHINGS_PER_NODE = 2;

    static int numberOfNodes;
    static Node[] nodes;


    public static void main(String[] args) throws IOException {
        setup();
        int answer = maximumBipartiteMatching();
        System.out.println(answer);
    }

    static void setup() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        setupNumberOfNodes(bufferedReader);
        setupNodes(bufferedReader);
    }


    static void setupNumberOfNodes(BufferedReader bufferedReader) throws IOException {
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        numberOfNodes = Integer.parseInt(stringTokenizer.nextToken());
    }

    static void setupNodes(BufferedReader bufferedReader) throws IOException {
        Shark[] sharks = new Shark[numberOfNodes];
        nodes = new Node[numberOfNodes];

        for (int i = 0; i < numberOfNodes; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            sharks[i] = new Shark();
            sharks[i].size = Long.parseLong(stringTokenizer.nextToken());
            sharks[i].speed = Long.parseLong(stringTokenizer.nextToken());
            sharks[i].intelligence = Long.parseLong(stringTokenizer.nextToken());

            nodes[i] = new Node();
            for (int j = 0; j < i; j++) {
                if (sharks[i].canEat(sharks[j])) {
                    nodes[i].connectedNodes.push(nodes[j]);
                }

                // 두 상어가 서로 잡아먹을 수 없도록 하기위해,
                // 동일한 체급의 상어에 대해 예외 처리.
                if (sharks[j].canEat(sharks[i]) && !sharks[j].isEqual(sharks[i])) {
                    nodes[j].connectedNodes.push(nodes[i]);
                }
            }
        }
    }

    static int maximumBipartiteMatching() {
        int numberOfRootNodes = 0;

        for (int i = 0; i < numberOfNodes; i++) {
            for (int j = 0; j < MATCHINGS_PER_NODE; j++) {
                clearMatchings();
                matchUsingDFS(nodes[i]);
            }
        }

        for (int i = 0; i < numberOfNodes; i++) {
            if (nodes[i].parentNode == null)
                numberOfRootNodes++;
        }
        return numberOfRootNodes;
    }

    static void clearMatchings() {
        for (int i = 0; i < numberOfNodes; i++) {
            nodes[i].isMatched = false;
        }
    }

    static boolean matchUsingDFS(Node node) {
        // 매칭에 성공하면 true를 반환한다.

        for (Node childNode : node.connectedNodes) {
            if (childNode.isMatched)
                continue;

            childNode.isMatched = true;
            if (childNode.parentNode == null || matchUsingDFS(childNode.parentNode)) {
                childNode.parentNode = node;
                return true;
            }
        }
        return false;
    }
}

Back to top