백준 1671 상어의 저녁식사

작성일 | In |

문제 링크

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

알고리즘

  • 이분 매칭

풀이

이분 매칭 응용문제다. ‘축사 배정’같은 이분 매칭 기본 문제만 풀다가 처음 맞닥뜨린 심화 문제였다.

성공하기까지 많은 시도를 했었고 실패를 했다.

문제에서 상어들이 서로를 잡아 먹기 위한 조건이 주어졌는데, 이 조건에 따라 상어들 간에 포식할 수 있는지 여부를 나타내는 인접 행렬을 구현하는 게 핵심 아이디어다.

인접 행렬로 상어마다 어떤 상어를 잡아 먹을 수 있는지 정리하는 데에 성공하면 이분 매칭을 실시하면 된다.

전체 코드

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
import sys
input = sys.stdin.readline

def sol(x):
    if visited[x]:
        return False
    
    visited[x] = 1
    
    for i in range(1, n+1):
        if check[x][i]:
            if not chain[i] or sol(chain[i]):
                chain[i] = x
                return True

    return False    



n = int(input())

lst = [[]]
for i in range(n):
    s, v, it = map(int, input().split())
    lst.append((s, v, it))
    
check = [[0] * (n+1) for _ in range(n+1)]
chain = [0] * (n+1)
    
    
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            continue
            
        if lst[i][0] == lst[j][0] and lst[i][1] == lst[j][1] and lst[i][2] == lst[j][2] and i > j:
            continue
            
        elif lst[i][0] >= lst[j][0] and lst[i][1] >= lst[j][1] and lst[i][2] >= lst[j][2]:
            check[i][j] = 1
    

for i in range(2):
    for j in range(1, n+1):
        visited = [0] * (n+1)
        sol(j)
    

print(chain[1:].count(0))