Uknow's Lab.
article thumbnail

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

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

 

난이도 : 골드 4
태그 : 구현, 백트래킹, 브루트포스, 시뮬레이션

 

 

1. 설명

기업 코테에서 정말 자주 나오는 문제 유형은 뭘까요?

사실 저도 기업코테를 많이 본 사람은 아니지만,

구현은 일단 안나온 적은 없었던 것 같고,

DFS/BFS/백트래킹도 정말 굉장히 자주 나왔던 것 같습니다.

구현 문제 중에서도 시뮬레이션 역시 단골 유형 중 하나인 것 같습니다.

분리집합/다익스트라 등도 좀 있던 것 같고요.

 

그런 의미에서 이번 문제는

백트래킹/브루트포스 + 구현 + 시뮬레이션이 섞인... 혼종이지만 코테 준비에는 꽤 좋을 것 같은 문제네요.

 

 

 

2. 소스코드

<kotlin />
import java.util.* import kotlin.math.min data class CCTV(val type: Int, val x: Int, val y: Int) lateinit var originMap: Array<Array<Int>> val cctv = ArrayList<CCTV>() var n = 0 var m = 0 var min = Int.MAX_VALUE fun main() = with(System.`in`.bufferedReader()) { val nm = readLine().split(" ").map { it.toInt() } n = nm[0] m = nm[1] originMap = Array(n) { x -> val st = StringTokenizer(readLine()) Array(m) { y -> val value = st.nextToken().toInt() if (value in 1..5) cctv.add(CCTV(value, x, y)) value } } backTracking(0, originMap) print(min) } fun backTracking(depth: Int, currentMap: Array<Array<Int>>) { if (depth == cctv.size) { val sum = currentMap.sumOf { it.count { it2 -> it2 == 0 } } min = min(min, sum) return } val cctvType = cctv[depth].type val maxDegree = when (cctvType) { 1, 3, 4 -> 4 2 -> 2 5 -> 1 else -> -1 } for (degree in 0 until maxDegree) { val copiedMap = Array(n) { x -> Array(m) { y -> currentMap[x][y] } } when (cctvType) { 1 -> cctvType1(cctv[depth], copiedMap, degree) 2 -> cctvType2(cctv[depth], copiedMap, degree) 3 -> cctvType3(cctv[depth], copiedMap, degree) 4 -> cctvType4(cctv[depth], copiedMap, degree) 5 -> cctvType5(cctv[depth], copiedMap) } backTracking(depth + 1, copiedMap) } } fun cctvType1(point: CCTV, map: Array<Array<Int>>, degree: Int) { when (degree) { // 오른쪽 0 -> watchRight(point, map) // 아래 1 -> watchDown(point, map) // 왼쪽 2 -> watchLeft(point, map) // 위 3 -> watchUp(point, map) } } fun cctvType2(point: CCTV, map: Array<Array<Int>>, degree: Int) { when (degree) { // 가로 0 -> { watchRight(point, map) watchLeft(point, map) } // 세로 1 -> { watchUp(point, map) watchDown(point, map) } } } fun cctvType3(point: CCTV, map: Array<Array<Int>>, degree: Int) { when (degree) { // 위, 오른쪽 0 -> { watchRight(point, map) watchUp(point, map) } // 오른쪽, 아래 1 -> { watchRight(point, map) watchDown(point, map) } // 아래, 왼쪽 2 -> { watchDown(point, map) watchLeft(point, map) } // 왼쪽, 위 3 -> { watchLeft(point, map) watchUp(point, map) } } } fun cctvType4(point: CCTV, map: Array<Array<Int>>, degree: Int) { when (degree) { // 오른쪽, 위, 아래 0 -> { watchRight(point, map) watchUp(point, map) watchDown(point, map) } // 왼쪽, 오른쪽, 아래 1 -> { watchLeft(point, map) watchRight(point, map) watchDown(point, map) } // 왼쪽, 위, 아래 2 -> { watchLeft(point, map) watchUp(point, map) watchDown(point, map) } // 위, 왼쪽, 오른쪽 3 -> { watchUp(point, map) watchLeft(point, map) watchRight(point, map) } } } fun cctvType5(point: CCTV, map: Array<Array<Int>>) { watchRight(point, map) watchLeft(point, map) watchUp(point, map) watchDown(point, map) } fun watchRight(p: CCTV, map: Array<Array<Int>>) { for (y in p.y until m) { if (map[p.x][y] == 6) break map[p.x][y] = -1 } } fun watchLeft(p: CCTV, map: Array<Array<Int>>) { for (y in p.y downTo 0) { if (map[p.x][y] == 6) break map[p.x][y] = -1 } } fun watchUp(p: CCTV, map: Array<Array<Int>>) { for (x in p.x downTo 0) { if (map[x][p.y] == 6) break map[x][p.y] = -1 } } fun watchDown(p: CCTV, map: Array<Array<Int>>) { for (x in p.x until n) { if (map[x][p.y] == 6) break map[x][p.y] = -1 } }

 

 

CCTV class는 CCTV의 타입, x, y 좌표를 담고 있는 클래스입니다.

watchUp, down, left, right는 각각 상 하 좌 우를 감시하는 메소드인데요.

벽 (6)을 만날 때 까지 탐색합니다.

cctv는 타입 1~5에 따라, 그리고 방향에 따라 watch 메소드들을 조합하여 감시합니다.

 

그리고, 모든 cctv의 각도에 대해 백트래킹을 적용하여 답을 탐색합니다.

이 과정에서, 매번 새로운 map을 복사하여 건네줍니다.

 

 

 

3. 후기

꽤... 오래 걸렸던 문제입니다.

구현 + 시뮬레이션 유형 특성 상 '아 이게 뭐지... 도저히 못풀겠다...' 보다는

'맞는데 왜 틀림?'을 외치며 예외를 잡아내는데 굉장히 많은 시간을 들였던 것 같습니다.

결국 정답을 받았지만 제출한 코드가 길고 중복되는 내용도 많아 맘에 들지 않아서,

watchUp/down/left/right 등 메소드로 나누고 이를 조합하는 방식으로 리팩토링 했는데, 조금 깔끔해진 것 같네요.

profile

Uknow's Lab.

@유노 Uknow

인생은 Byte와 Double 사이 Char다. 아무말이나 해봤습니다.