백준 1671 <상어의 저녁식사> Python

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

---

유명한 이분매칭 문제입니다.

살아남을 수 있는 상어수의 최솟값을 구하라는 말은 가장 많이 잡아먹힌 케이스를 구하라는 말과 같고 최대한 많이 매칭하라는 말과 같으므로 이분매칭으로 풀 수 있습니다. 

한 마리의 상어가 두 마리 까지 잡아먹을 수 있다는 점에서

https://dev-diary-0717.tistory.com/172

의 열혈강호 2 와 비슷한 문제입니다.

이번에는 포스팅한 방식이 아닌 그저 이분매칭을 두 번 돌리는 방식으로 풀었습니다.

또 주의해야 할 케이스가 서로를 잡아먹는 케이스인데, visited 를 조작하는 방식보다는 데이터를 서로 잡아먹을 수 없게 만들어놓는 것이 보다 편합니다.

---

import sys

input = sys.stdin.readline

# 이분매칭

def bimatch(idx, connectable, visited, connected):

    # 이미 체크한 수이면

    if visited[idx]:

        return False

    # 체크

    visited[idx] = True

    # 연결될 수 있는 수 목록 순회

    for node in connectable[idx]:

        # 연결될 수 있는 수 이거나 다른 수와 연결할 수 있으면

        if connected[node] < 0 or bimatch(connected[node], connectable, visited, connected):

            # 연결

            connected[node] = idx

            return True

    return False

def solution(N, state_list):

    # 연결 가능한 목록

    connectable = [[] for _ in range(N)]

    # 순회하며 연결 가능한 목록 만들기

    for i in range(N-1):

        for j in range(i+1, N):

            # 잡아먹을 수 있으면

            if all([state_list[i][idx] >= state_list[j][idx] for idx in range(3)]):

                connectable[i].append(j)

            elif all([state_list[i][idx] <= state_list[j][idx] for idx in range(3)]):

                connectable[j].append(i)

    # 연결 목록

    connected = [-1 for _ in range(N)]

    # 순회하며 이분매칭

    for idx in range(N):

        # 두 마리까지 먹을 수 있음

        for _ in range(2):

            # 방문목록

            visited = [False for _ in range(N)]

            # 이분매칭

            bimatch(idx, connectable, visited, connected)

    print(sum([1 for c in connected if c < 0]))

# 입력

N = int(input().strip())

state_list = [list(map(int, input().strip().split())) for _ in range(N)]

solution(N, state_list)