백준 18428 감시 피하기
16 Dec 2021N이 최대 6이기 때문에 브루트포스를 사용해야 함을 짐작할 수 있다. 모든 비어있는 공간에 대하여 3개의 Object를 배치시키고 모든 선생님들이 학생을 감시할 수 없는 경우가 하나라도 있는지 확인하면 된다. Object 3개를 배치하는 것은 순열을 통해 모든 경우를 확인해주면 된다.
- 전체 코드
import Foundation
let n = Int(readLine()!)!
var board: [[String]] = []
var empty: [(x: Int, y: Int)] = []
var teacher: [(x: Int, y: Int)] = []
var possibleCount = 0
(0..<n).forEach { yIndex in
let line = readLine()!.split(separator: " ").map{ String($0) }
(0..<n).forEach { xIndex in
if line[xIndex] == "X" { empty.append((xIndex, yIndex)) }
if line[xIndex] == "T" { teacher.append((xIndex, yIndex)) }
}
board.append(line)
}
empty.indices.forEach { index in makeObject(index: index, count: 0) }
print(possibleCount != 0 ? "YES" : "NO")
func findStudent(x: Int, y: Int) -> Bool {
let dx = [1, -1, 0, 0]
let dy = [0, 0, 1, -1]
loop: for i in 0...3 {
var nextX = x + dx[i]
var nextY = y + dy[i]
while (0..<n) ~= nextX && (0..<n) ~= nextY {
switch board[nextY][nextX] {
case "S":
return true
case "T", "O":
continue loop
default:
break
}
nextX += dx[i]
nextY += dy[i]
}
}
return false
}
func makeObject(index: Int, count: Int) {
if count == 3 {
let result = teacher.map{ findStudent(x: $0.x, y: $0.y) }.contains(true)
if !result { possibleCount += 1 }
return
}
let position = empty[index]
for i in index+1..<empty.count {
board[position.y][position.x] = "O"
makeObject(index: i, count: count + 1)
board[position.y][position.x] = "X"
}
}