백준 15683 감시

출처: www.acmicpc.net/problem/15683

분류: 완전탐색

---

접근방식

하.. 코드량이 너무 너무 너무 길었던 문제였습니다.

5개의 CCTV가 있고 각 CCTV는 90도로 회전이 가능합니다.
사각지대가 가장 최소가 되는 경우를 찾는 문제입니다.

각 CCTV 의 케이스는
1번 상하좌우 4개
2번 상하, 좌우 2개
3번 4개
4번 4개
5번 1개

입니다. 

저는 CCTV를 먼저 찾아놓고 CCTV List를 다 탐색할 때 까지 DFS를 돌렸습니다.

CCTV 에 케이스는 많지만 결국 지우는 건 방향에 따라 상하좌우 4가지 이므로 상하좌우 direction을 입력받는 함수를 만들어서 지우고
CCTV 타입별로 상 하 좌 우로 직접 입력해주는 방식을 사용했습니다.

더 스마트하게 풀 수도 있을 것 같은데 좀 무식하게 푼 것 같네요ㅠ
board를 계속 복사해서 그런지 시간이 꽤 걸렸네요..
어렵다기보다는 꽤나 귀찮았던 문제였습니다.

 

해결방법

let nm = readLine()!.split(separator: " ").map{Int($0)!}
var board = [[Int]]()
for _ in 0..<nm[0] {
    board.append(readLine()!.split(separator: " ").map({Int($0)!}))
}
var minBlindArea = Int.max
typealias CCTV = (r: Int, c: Int, type: Int)
enum Direction {
    case up
    case down
    case right
    case left
}
var cctvList = [CCTV]()

for r in 0..<board.count {
    for c in 0..<board[0].count {
        if board[r][c] == 0 || board[r][c] == 6 { continue }
        cctvList.append(CCTV(r: r, c: c, type: board[r][c]))
    }
}

func makeSafeArea(row: Int, col: Int, direction: Direction, board: [[Int]]) -> [[Int]] {
    var r = row
    var c = col
    var board = board
    
    switch direction {
    case .up:
        while 0..<board.count ~= r-1  {
            r -= 1
            if board[r][c] == 6 {
                return board
            } else if board[r][c] == 0 {
                board[r][c] = -1
            } else {
                continue
            }
        }
        return board
    case .down:
        while 0..<board.count ~= r+1  {
            r += 1
            if board[r][c] == 6 {
                return board
            } else if board[r][c] == 0 {
                board[r][c] = -1
            } else {
                continue
            }
        }
        return board
    case .left:
        while 0..<board[0].count ~= c-1  {
            c -= 1
            if board[r][c] == 6 {
                return board
            } else if board[r][c] == 0 {
                board[r][c] = -1
            } else {
                continue
            }
        }
        return board
    case .right:
        while 0..<board[0].count ~= c+1  {
            c += 1
            if board[r][c] == 6 {
                return board
            } else if board[r][c] == 0 {
                board[r][c] = -1
            } else {
                continue
            }
        }
        return board
    }
}

func checked(cctv: CCTV, board: [[Int]]) -> [[[Int]]] {
    var boards = [[[Int]]]()
    switch cctv.type {
    case 1:
        boards.append(makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: board))
        boards.append(makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: board))
        boards.append(makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: board))
        boards.append(makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: board))
    case 2:
        var leftBoard = board
        leftBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: leftBoard)
        leftBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: leftBoard)
        boards.append(leftBoard)
        
        var upDownBoard = board
        upDownBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: upDownBoard)
        upDownBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: upDownBoard)
        boards.append(upDownBoard)
    case 3:
        var tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: tempBoard)
        boards.append(tempBoard)
        
        tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: tempBoard)
        boards.append(tempBoard)
        
        tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: tempBoard)
        boards.append(tempBoard)
        
        tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: tempBoard)
        boards.append(tempBoard)
    case 4:
        var tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: tempBoard)
        boards.append(tempBoard)
        
        tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: tempBoard)
        boards.append(tempBoard)
        
        tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: tempBoard)
        boards.append(tempBoard)
        
        tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: tempBoard)
        boards.append(tempBoard)
    case 5:
        var tempBoard = board
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .left, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .up, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .right, board: tempBoard)
        tempBoard = makeSafeArea(row: cctv.r, col: cctv.c, direction: .down, board: tempBoard)
        boards.append(tempBoard)
    default: break
    }
    return boards
}

func check(index: Int, board origin: [[Int]]) {
    if index >= cctvList.count {
        var blind = 0
        for row in origin {
            blind += row.filter({ $0 == 0 }).count
        }
        minBlindArea = min(minBlindArea, blind)
        return
    }
    
    let cctv = cctvList[index]
    for board in checked(cctv: cctv, board: origin) {
        check(index: index+1, board: board)
    }
}
check(index: 0, board: board)
print(minBlindArea)

 

배운점

하아... 진빠진다..