boj, 백준) 2051. 최소 버텍스 커버 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2051 2051번: 최소 버텍스 커버 A와 B로 나누어져 있는 이분 그래프가 입력으로 주어진다. A에는 정점이 N개가 있고, B에는 정점이 M개가 있다. 정점은 A의 정점은 1번부터 N번, B의 정점도 1번부터 M번가지 번호가 매겨져 있다. A의 www.acmicpc.net 2. 문제 개요 이분 그래프의 최소 버텍스 커버(Minimum Vertex Cover)를 구하는 프로그램을 작성하시오. 단, 어떤 Node들이 Vertec cover를 구성하는지 출력할 것. 3. 문제 힌트 쾨닉의 정리에 의해서 최소 버텍스 커버 C의 개수는 이분 매칭의 최대 매칭 값 M과 같다. 어떤 노드들이 버텍스 커버C를 구성하는지 구하는 방법은 C = ..
백준, boj) 1867. 돌멩이 제거 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 문제 n행 n열의 격자로 나뉜 운동장이 있다. 이 위에 k개의 돌멩이가 있는데, 하나의 돌멩이는 격자 한 칸에 정확히 들어가 있으며, 두 개 이상의 돌멩이가 한 칸에 들어가 있는 경우는 없다. 사고의 위험을 없애기 위해 이 돌멩이를 모두 제거하고 깨끗한 운동장을 만들려고 한다. 돌멩이를 제거할 때에는, 한 행이나 한 열을 따라 직선으로 달려가면서 그 행이나 열에 놓인 돌멩이를 모두 줍는 방식을 쓴다. 여러분이 할 일은 운동장의 상태가 주어졌을 때 최소 몇 www.acmicpc.net 2. 문제 개요 한 번에 하나의 행이나, 하나의 열 중 하나를 골라서 정리할 때, 최소로 움직여서 모든 돌을 치우는 ..