[백준] 15683 감시 삼성 SW 역량 테스트 기출 문제

https://www.acmicpc.net/problem/15683

15683번: 감시

 

후기 : 골드 4 수준은 절대 아닙니다~ 제 생각엔 골드 1정도. 문제 자체도 카메라가 많아서 솔직히 좀 지저분한 문제라는 생각이 들고 코드량도 많아지기 때문. 더군다나 중복체크를 허용하는 백트랙킹을 3번씩하는 것은 구현하거나 생각해내기가 상당히 어려웠다는 점에서 난이도도 있고 배울 점도 있었지만 딱~히 교육적인 문제라는 생각은 안드는 문제. (삼성에서 이런 비효울적인 문제를 테스트로 내는 이유는 뭘까...?) 풀면서 제일 크게 느낀 점은 카메라 갯수 좀 줄였으면 꽤 괜찮은 문제였을텐데.... 였음 -> 아~ 그렇구나 하고 넘어가는게 낫지 용써서 풀만한 문제는 아닌듯. 영양가x

 

풀이 : 백트랙킹으로 모든 카메라를 3번씩 체크하는 방식 사용. 

ex) 1번 카메라 0번 돌리고 범위체크 -> 1번 카메라 1번 돌리고 범위체크 -> ..... -> 1번 카메라 3번 돌리고 2번 카메라 0번 돌리고 범위체크 -> 반복. 

풀고나서 확인해보니 다른 분들은 dfs나 다른 방법으로 푸는 것으로 보이는데, 제가 좀 특이한듯.. 선호하는 방식으로 푸시면 될듯.

dfs 또한 카메라를 순회하면서 모든 카메라에 대해 탐색을 시도할 때 for문(4방향)을 넣어서 전체탐색하는 듯.

결론적으론 백트랙킹이랑 똑같음.

 

package backtracking.b15683_point_hardest

import java.util.LinkedList

val br = System.`in`.bufferedReader()
val getLine get() = br.readLine().split(" ").map { it.toInt() }
var yy = 0
var xx = 0
lateinit var map : Array<IntArray>
lateinit var cam : IntArray
val camQue = LinkedList<C>()

data class C(
    val y:Int,
    val x:Int,
    val type: Int
)

fun isRange(y:Int,x:Int) = y in 0 until yy && x in 0 until xx

var res = Int.MAX_VALUE

fun move(m: Array<IntArray>, dir:Int, sy:Int, sx:Int){
    var dy = sy
    var dx = sx
    when(dir){
        0 -> while (true){
            dy -= 1
            if (!isRange(dy, dx) || m[dy][dx] == 6) break
            m[dy][dx] = -1
        }

        1 -> while (true) {
            dx += 1
            if (!isRange(dy, dx) || m[dy][dx] == 6) break
            m[dy][dx] = -1
        }

        2 -> while (true) {
            dy += 1
            if (!isRange(dy, dx) || m[dy][dx] == 6) break
            m[dy][dx] = -1
        }

        3 -> while (true) {
            dx -= 1
            if (!isRange(dy, dx) || m[dy][dx] == 6) break
            m[dy][dx] = -1
        }
    }
}

fun cal(): Int {
    val m = Array(yy){IntArray(xx)}
    for(y in 0 until yy)
        for(x in 0 until xx) m[y][x] = map[y][x]

    for(c in camQue){
        val (cy,cx,ct) = c
        m[cy][cx] = -1
        val idx = cy*xx+cx

        when(ct){
            1 -> move(m,(cam[idx]+1)%4,cy,cx)

            2 -> if(cam[idx]%2 == 0) {
                move(m, 1, cy, cx)
                move(m, 3, cy, cx)
            } else {
                move(m, 0, cy, cx)
                move(m, 2, cy, cx)
            }

            3 -> {
                move(m, cam[idx], cy,cx)
                move(m, (cam[idx]+1)%4, cy,cx)
            }

            4 -> {
                move(m,if(cam[idx]-1 == -1) 3 else cam[idx]-1,cy,cx)
                move(m,cam[idx],cy,cx)
                move(m,(cam[idx]+1)%4,cy,cx)
            }

            5 -> for(r in 0..3) move(m,r,cy,cx)
        }
    }
    var cnt = 0
    for(y in 0 until yy)
        for(x in 0 until xx) if(m[y][x] == -1 || m[y][x] == 6) cnt++

    return yy*xx-cnt
}

fun rotateCam(idx: Int){ // todo 3이 최대일 경우 -> 00 10 20 30 31 32 33 21 22 23 11 12 13 01 02 03 처럼 3번씩 고르는 모든 경우를 백트랙킹. (기존 백트랙킹과 비슷하지만 다른 방식으로 활용)

    res = minOf(res,cal())

    for(r in idx until yy*xx){
        val y = r/xx //todo 2차원 배열을 1차원으로 변환할 때 y,x 좌표 모두 x좌표를 활용하여 구할 수 있다.
        val x = r%xx

        if(map[y][x] in 1..5 && cam[r] < 3){
            cam[r]++
            rotateCam(r)
            cam[r]--
        }
    }
}

fun main(){
    getLine.let {
        yy = it[0]
        xx = it[1]

        map = Array(yy){ IntArray(xx) }
        cam = IntArray(yy*xx)

        for(y in 0 until yy){
            val p = getLine
            for(x in 0 until xx) {
                if(p[x] in 1..5) camQue.add(C(y,x,p[x]))
                map[y][x] = p[x]
            }
        }

        rotateCam(0)
        println(res)
    }
}