백준 11014 컨닝 2
23 Jun 2021https://www.acmicpc.net/problem/11014
NxM의 배열이 주어지면 x표시가 아닌 자리에 학생들을 배치시킨다고 하자. 이 때 학생이 좌측, 우측, 좌측상단, 우측상단에 다른 학생이 위치하면 컨닝을 할 수 있다고 했을 때 아무도 컨닝을 할 수 없도록 하면서 배치할 수 있는 학생의 최대 수를 구하는 문제이다.
핵심 포인트는 바로 옆 열에 위치한 학생들끼리만 컨닝이 가능하는 것이다. 따라서 홀수 열에 해당하는 자리는 그룹 A로 짝수 열에 해당하는 자리를 그룹 B로 나누어 이분매칭 그래프를 그려보자.
우리는 되도록 홀수열에 학생을 무조건 앉히고 만약 짝수열에도 자리를 앉힐 수 있다면 앉히도록 할 것이다. 이 때 구해지는 최대 매칭은 홀수열에 학생들을 배치 시켰을 때 앉을 수 없는 짝수열 자리의 수와 같다는 것이다. 이 때 그래프를 그릴 때 x표시가 된 자리는 그래프에 그려주지 않도록 한다. 최종적으로 구하는 결과는 전체 자리의 수에서 x표시가 된 자리의 갯수와 최대 매칭으로 구한 자리의 수를 빼주면 된다.
- 전체 코드
var left:[(Int, Int)] = []
var right:[(Int, Int)] = []
var left2right:[[Int]] = []
var check:[Bool] = []
var right2left:[Int] = []
func isNear(a: (Int, Int), b: (Int, Int)) -> Bool {
let dx = a.0 - b.0
let dy = a.1 - b.1
return dx*dx+dy*dy <= 2
}
func dfs(leftIdx: Int) -> Bool {
for rightIdx in left2right[leftIdx] {
if check[rightIdx] {
continue
}
check[rightIdx] = true
if right2left[rightIdx] == -1 || dfs(leftIdx: right2left[rightIdx]) {
right2left[rightIdx] = leftIdx
return true
}
}
return false
}
let t = Int(readLine()!)!
var str = ""
for _ in 0..<t {
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
var xCount = 0, result = 0
left = []
right = []
for i in 0..<n {
let line = readLine()!.map{Character(String($0))}
for j in 0..<line.count {
if line[j] == "." {
if j%2 == 0 {left.append((i, j))}
else {right.append((i, j))}
}
else {xCount += 1}
}
}
let rcount = right.count, lcount = left.count
left2right = Array(repeating: [], count: lcount)
check = Array(repeating: false, count: rcount)
right2left = Array(repeating: -1, count: rcount)
for i in 0..<lcount {
for j in 0..<rcount {
if isNear(a: left[i], b: right[j]) {
left2right[i].append(j)
}
}
}
for idx in 0..<lcount {
check = Array(repeating: false, count:rcount)
if dfs(leftIdx: idx) {
result += 1
}
}
str += "\(n*m-xCount-result)\n"
}
print(str)