백준 2339 석판 자르기
09 Nov 2021분할정복의 일종으로 불순물이 있는 곳을 중점으로 자른 후 양쪽으로 구역이 나뉘었을 때 좌측/우측의 경우의 수를 구해 곱해주면 해결할 수 있다.
이 때 문제의 조건이 몇가지 존재한다.
- 항상 첫번째 자른 방향과 다른 방향으로 다음번에 잘라야한다.
- 불순물을 기준으로 자를때 해당 선분에 보석이 존재해서는 안된다. 이 때 다른 불순물이 존재하는 것은 상관없다.
- 최종적으로 나뉘어진 각각의 조각에는 보석이 1개씩 존재해야한다. 없어서는 안된다.
따라서 우리는 분할정복을 하는 함수를 구현할 때 Board상에서 범위의 최솟값과 최댓값을 받아야하고 수직으로 잘라야하는지 수평으로 잘라야하는지 여부를 같이 받아야한다. 만약 min값이 max값보다 큰 경우가 존재할 경우 해당 영역은 존재하지 않기 때문에 1을 return해주어 경우의수를 구하는데 오류가 생기지 않도록 해준다.
그 후 다음과 같이 영역의 조건을 확인해주고 필요한 경우 분할정복을 다시 적용하여 경우의 수를 계산해주자. 최종적으로 전체 범위에 대해 수직, 수평 각각에 대해서 적용한 것을 더해주면 모든 경우의 수를 구할 수 있다.
- 보석 1개만 존재 -> 성공 (return 1)
- 보석 0개 혹은 보석 2개 이상 && 불순물 0 -> 실패 (return 0)
- 그 외 경우 (다시 분할정복 적용)
- 전체 코드
//
// main.swift
// testttt
//
// Created by 강현준 on 2021/11/09.
//
import Foundation
let n = Int(readLine()!)!
var board: [[Int]] = []
(0..<n).forEach { _ in
let line = readLine()!.split(separator: " ").map { Int($0)! }
board.append(line)
}
let vertical = calc(min: (0, 0), max: (n-1, n-1), isVertical: true)
let horizontal = calc(min: (0, 0), max: (n-1, n-1), isVertical: false)
print((vertical + horizontal > 0) ? vertical + horizontal : -1)
func calc(min: (Int, Int), max: (Int, Int), isVertical: Bool) -> Int {
if min.0 > max.0 || min.1 > max.1 { return 1 }
var goods: [(Int, Int)] = []
var bads: [(Int, Int)] = []
for i in min.0...max.0 {
for j in min.1...max.1 {
if board[i][j] == 2 { goods.append((i, j)) }
if board[i][j] == 1 { bads.append((i, j)) }
}
}
if goods.count == 1 && bads.count == 0 {
return 1
} else if goods.count == 0 || (goods.count > 1 && bads.count == 0) {
return 0
} else {
var result = 0
bads.forEach { bad in
guard !goods.contains(where: { good in isVertical ? bad.0 == good.0 : bad.1 == good.1 })
else { return }
let left = calc(
min: min,
max: isVertical ? (bad.0-1, max.1) : (max.0, bad.1-1),
isVertical: !isVertical
)
let right = calc(
min: isVertical ? (bad.0+1, min.1) : (min.0, bad.1+1),
max: max,
isVertical: !isVertical
)
result += left*right
}
return result
}
}