[프로그래머스][level3] 기둥과 보 설치 (Kotlin)

https://programmers.co.kr/learn/courses/30/lessons/60061

코딩테스트 연습 - 기둥과 보 설치

 

[난이도] level3
[유형] 구현

[풀이]
3차원 배열 map[202][202][2]를 선언하여
map[x][y][0] == true 이면 (x,y)~(x,y+1) 기둥이 설치된 것
map[x][y][1] == true 이면 (x,y)~(x+1,y) 보가 설치된 것
위와 같이 관리하도록 하였습니다.

이제 기둥과 보를 각각 설치할때 이것을 설치할 수 있는지와
제거할 때 제거할 수 있는지를 체크해야 합니다.

설치하는 할때 확인하는 것은 쉽습니다.
기둥의 경우 바닥인지, 아래 기둥이 있는지, 보가 있는지만 확인하면 설치가 가능하고
보의 경우 아래 기둥이 있는지, 양옆에 보가 있는지만 확인하면 됩니다.

하지만 제거할 때는 문제가 복잡해질 수도 있습니다.
특정 위치 (x,y)의 기둥이나 보를 제거한다고 할때,
"(x+b,y+b)에 기둥이나 보가 있으니까 (x,y)를 제거하면 안돼" 이렇게 생각하면 복잡해 지는 경우입니다.
단순하게
"(x,y)의 기둥(보) 를 지웠음에도 map의 모든 기둥과 보가 조건을 만족하고 있다면 (x,y)는 지워도 되겠네"
라고 생각하는 것이 좋습니다.

즉, (x,y)의 기둥(보)를 지워보고 nxn map의 모든 기둥봐 보를 2중 for문으로 체크해보면서 조건을 여전히 만족하는지를 체크하는 것입니다.

쿼리가 1000개이고 n이 최대 100이기 때문에 O(100x100x10000) 으로 충분히 시간내에 해결이 가능합니다.
만약 n이 좀더 큰수라면 지워야하는 (x,y)의 주변에 영향을 받을만한 (x+b,y+b)들만 체크해야 겠지만
n이 작아 생각할 필요가 없기 때문에 전체 점을 체크하였습니다.

(x,y) 위치의 기둥은 checkFunc[0](x,y), 보는 checkFunc[1](x,y) 로 체크할 수 있도록
lamda list를 만들었습니다 (0,1로 연결지을 수 있도록)

check 함수는 전체 점을 체크하는 함수입니다. 이곳에서 checkFunc를 사용하여 (x,y)를 제거했을 때 전체 점이
여전히 조건을 만족하면 true 아니면 false를 return합니다.

입력받은 x,y에 1씩 더하여 map을 +1,+1씩 평행이동 시켰다고 생각하고 풀면 index 범위 체크를 하지 않아도 됩니다.

 

var map = Array(202){Array(202){BooleanArray(2)}}
var checkFunc = listOf(
    {x:Int,y:Int -> y==1 || map[x][y-1][0] || map[x-1][y][1] || map[x][y][1]},
    {x:Int,y:Int -> (map[x-1][y][1] && map[x+1][y][1]) || map[x][y-1][0] || map[x+1][y-1][0] }
)
fun check(x:Int,y:Int,n:Int):Boolean{
    for(i in 1..n+1)
        for(j in 1..n+1){
            if(map[i][j][0] && !checkFunc[0](i,j)) return false
            if(map[i][j][1] && !checkFunc[1](i,j)) return false
        }
   return true
}
class Solution {
    fun solution(n: Int, build_frame: Array<IntArray>): Array<IntArray> {
        for((tx,ty,a,b) in build_frame){
            var x = tx+1
            var y = ty+1
            if(b==0){
                map[x][y][a]=false
                if(!check(x,y,n)) map[x][y][a]=true
            }else{
                if(checkFunc[a](x,y)) {
                    map[x][y][a]=true
                }
            }
        }
        var lst = mutableListOf<IntArray>()
        for(i in 1..n+1){
            for(j in 1..n+1){
                if(map[i][j][0]) lst.add(intArrayOf(i-1,j-1,0))
                if(map[i][j][1]) lst.add(intArrayOf(i-1,j-1,1))
            }
        }
        return lst.toTypedArray()
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/기둥과_보_설치.cpp