백준_1671_상어의 저녁식사

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

1671번: 상어의 저녁식사

해결 방법

> 상어의 먹이사슬 관계를 잘 파악해야 한다.

> 각 상어를 노드로 생각한다.

> 상어가 다른 상어를 잡아먹을수 있는 수는 최대 2마리이다.(용량이 2)

> 잡아먹힌 상어는 더이상 잡아먹힐 수 없다.(용량 1)

http://blog.naver.com/kks227/220469070147

 

 

코드

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))