백준_1671_상어의 저녁식사
https://www.acmicpc.net/problem/1671
1671번: 상어의 저녁식사
어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다. 그러나, 상어들의 왕 김재홍은 상어들이 많이 없어지는 것을 방지하기 위해서 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다. 상어들은 김재홍의 말을 모두 듣는다. N마리 상어의 크기, 속도, 지능이 주어졌
www.acmicpc.net
해결 방법
> 상어의 먹이사슬 관계를 잘 파악해야 한다.
> 각 상어를 노드로 생각한다.
> 상어가 다른 상어를 잡아먹을수 있는 수는 최대 2마리이다.(용량이 2)
> 잡아먹힌 상어는 더이상 잡아먹힐 수 없다.(용량 1)
코드
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
num_shark = int(input())
food_chain = dict() #먹이 사슬의 정보를 저장하기 위한 dict
for i in range(1, num_shark + 1):
food_chain[i] = list()
shark_info = list() #입력 값 중 상어의 정보를 저장
for i in range(num_shark):
shark_info.append(list(map(int, input().split())))
#상어의 크기, 속도, 지능의 대소를 비교하여 먹이사슬(dict)에 저장하기 위한 부분
'''
for i in range(num_shark):
for j in range(num_shark):
if i != j and shark_info[i][0] >= shark_info[j][0] and shark_info[i][1] >= shark_info[j][1] and shark_info[i][2] >= shark_info[j][2]:
if shark_info[i][0] == shark_info[j][0] and shark_info[i][1] == shark_info[j][1] and shark_info[i][2] == shark_info[j][2]:
food_chain[i + 1].append(j + 1)
food_chain[j + 1].append(i + 1)
else:
food_chain[i + 1].append(j + 1)
'''
for i in range(num_shark):
for j in range(num_shark):
if i == j:
continue
if shark_info[i][0] < shark_info[j][0] or shark_info[i][1] < shark_info[j][1] or shark_info[i][2] < shark_info[j][2]:
continue
if shark_info[i][0] == shark_info[j][0] and shark_info[i][1] == shark_info[j][1] and shark_info[i][2] == shark_info[j][2] and i > j:
continue
food_chain[i + 1].append(j + 1)
food_chain_list = list(food_chain.items())
#포드 풀커슨을 위한 파이프(int로 초기화)
pipe = defaultdict(lambda:defaultdict(int))
#source(여기에서는 0)과 상어들을 용량이 2(상어가 잡아먹을 수 있는 최대 수)인 파이프로 연결
for i in range(1, num_shark + 1):
pipe[0][i] += 2
#상어가 다른 상어를 잡아먹는 경우 -> 용량이 1
for i in food_chain_list:
for j in i[1]:
pipe[i[0]][j + num_shark] += 1
#잡아먹힌 상어들이 sink로 유량 1을 보내주는 부분, num_shark*2+1 -> sink
for i in range(num_shark + 1, num_shark * 2 + 1):
pipe[i][num_shark*2+1] += 1
#유량을 흘려보낼 수 있는지 판단하는 bfs
def bfs(start, sink, parent):
visited = defaultdict(lambda:0)
queue = deque()
queue.append(start)
visited[start] = 1
while queue:
u = queue.popleft()
for i in pipe[u]:
val = pipe[u][i]
if visited[i]:
continue
if val <= 0:
continue
queue.append(i)
visited[i] = 1
parent[i] = u
return 1 if visited[sink] else 0
def ford_fulkerson(start, sink):
parent = defaultdict(lambda : -1)
max_flow = 0
while bfs(start, sink, parent):
path_flow = float('inf')
s = sink
while s!= start:
path_flow = min(path_flow, pipe[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while v != start:
u = parent[v]
pipe[u][v] -= path_flow
pipe[v][u] += path_flow
v = parent[v]
return max_flow
'''
ex)포드 풀커슨의 값이 3이라면 잡아먹힌 상어의 수가 3마리 이므로 전체 상어의 수에서
빼주어야 원하는 값이 나온다.
'''
print(num_shark - ford_fulkerson(0,num_shark*2+1))