oVeron

1.쥐가 전부 구멍에 들어갈 수 있는지에 따라 답을 출력하는 문제이다. 일단  쥐를 최대한 많이 구멍에 들어가게 해야 하므로, 구멍에 들어가는 쥐의 수를 하나의 유량으로 생각하여 최대 유량 문제로 바꿔 풀어보자. 먼저 쥐들과 구멍들을 하나의 간선으로 연결한다. 간선의 용량은 당연히 \(1\)이 될 것이다.\(source\)와 쥐들을 간선으로 연결할 때도 간선의 용량은 당연히 \(1\)이 된다.구멍들과 \(sink\)를 간선으로 연결해 보자. 각 구멍에 들어갈 수 있는 쥐의 수는 \(k\)이므로, 간선의 용량은 \(k\)가 된다. 이 정보들을 종합해 그래프를 구현한 후, 최대 유량 알고리즘을 적용하면 문제를 풀 수 있다. 2.문제는 어떤 쥐들과 구멍들을 간선으로 연결할 지 정하는 것이다. 쥐와 구멍의 좌표..

알고리즘/baekjoon 2024. 6. 30. 10:17