백준 18428 감시 피하기

문제 보러 가기

N이 최대 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"
    }
}