[JS] 블록 게임 [2019 카카오]

까다로운 2차원 빡구현문제였다. 개인적으로 이런 2차원 문제를 좋아하기에 나름 재밌게 풀었다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42894

프로그래머스

 

 

코드는 꽤나 복잡하지만 내가 푼 방법을 정리하면 아래와 같다.

 

1. 12개의 퍼즐이 있다고 생각하고 각 퍼즐의 정보를 배열로 저장했다. (dR,dC 활용)

이때 통일성을 주기 위해서 시작점은 최상단 중에서 가장 왼쪽에 있는 것으로 했다. 그래야 탐색할때 첫지점을 찾기 편하다.

 

2. 모든 타일의 dR,dC정보가 담긴 pR,pC 배열을 만들고 해당 타일의 index를 타입이라고 생각하기로 했다.

위부터 퍼즐의 타입이 0,1,2,3순으로 되게 저장

3. Map 자료형을 통해서 key : 퍼즐번호(num) , val : [ 시작점의 R, 시작점의 C, 타일 Type ] 으로 저장한다.

문제에서 제공한 예시대로 저장한다면 아래와 같이 나올 것이다.

	Map(5) {
  4 => [ 4, 6, 11 ],
  3 => [ 6, 4, 5 ],
  2 => [ 7, 3, 6 ],
  5 => [ 7, 8, 7 ],
  1 => [ 8, 0, 2 ]
}

즉 1번 번호를 가진 퍼즐은 [8,0]에 시작점을 둔 2번 타입 (ㄴ자 모양) 이란 정보를 가지고 있다.

 

4. 퍼즐 중에서 제거 자체가 불가능한 타일들이있다. 2,3,5,6,8 번 타일만이 위에서 블록을 쌓아서 직사각형을 만들 수 있으므로 해당 정보를 저장해준다.

 const isAblePuzzle = [0,0,1,1,0,1,1,0,1,0,0,0]
 // isAblepuzzle[i] => type이 i인 퍼즐이 제거할 수 있는 퍼즐인지 정보 제공

 

5. 제거할 수 있는 퍼즐들을 검사할 수 있는 dR,dC를 생각해준다.

예를들어 Type이 2인 퍼즐(ㄴ자) 를 없애기 위해서는 시작점 기준으로 [0,1] , [0,2] 에 블럭을 쌓을 수 있는 지 파악해야 한다.

나머지 제거 가능한 타입들도 경우의 수를 생각해서 아래와 같이 써준다.

//삭제할때 위가 뚫려있는지 확인해야 하는 부분 정보
    const deleteR = [0,0,[0,0],[1],0,[1],[0,0],0,[0,0],0,0,0]
    const deleteC = [0,0,[1,2],[-1],0,[1],[-2,-1],0,[-1,1],0,0,0]

 

 

6. 5번을 활용하여 특정 num의 타일이 현재 제거할 수 있는 상태인지 파악하는 함수를 만든다.

 

7. 현재 board의 퍼즐 중에서 제거가 가능한 타일들만 Map으로 저장한다. 예시를 들면 아래와 같다.

key : num , val = [ 시작 R, 시작 C , 퍼즐 타입 ]

	Map(3) { 3 => [ 6, 4, 5 ], 2 => [ 7, 3, 6 ], 1 => [ 8, 0, 2 ] }

 

8. 이 Map을 순회하며 제거할 수 있다면 board에서 퍼즐을 제거한다. 해당 과정은 map에 변화가 없을때까지 반복한다.

 

9. 처음 제거를 시작했을때 Map의 사이즈와 최종적으로 남은 Map의 사이즈의 차를 반환하면 결과가 나온다.

 

 

function solution(board) {
    const {length} = board
    
    //퍼즐정보 저장
    const firstR = [[0,0,0,1],[0,0,1,2],[0,1,1,1],[0,1,2,2]]
    const firstC = [[0,1,2,2],[0,1,0,0],[0,0,1,2],[0,0,0,-1]]
    const secondR = [[0,0,0,1],[0,1,2,2],[0,1,1,1],[0,0,1,2]]
    const secondC = [[0,1,2,0],[0,0,0,1],[0,-2,-1,0],[0,1,1,1]]
    const thirdR = [[0,1,1,1],[0,1,1,2],[0,0,0,1],[0,1,1,2]]
    const thirdC = [[0,-1,0,1],[0,0,1,0],[0,1,2,1],[0,-1,0,0]]
    
    const pR = [...firstR,...secondR,...thirdR]
    const pC = [...firstC,...secondC,...thirdC]
    
    //삭제할때 위가 뚫려있는지 확인해야 하는 부분 정보
    const deleteR = [0,0,[0,0],[1],0,[1],[0,0],0,[0,0],0,0,0]
    const deleteC = [0,0,[1,2],[-1],0,[1],[-2,-1],0,[-1,1],0,0,0]
    
    //완성이 가능,불가능한 퍼즐 정보 생성
    const isAblePuzzle = [0,0,1,1,0,1,1,0,1,0,0,0]
    // r,c가 유효한 보드 범위 내인지
    const isCanGo = (r,c) => 0<=r&&r<length&&0<=c&&c<length

    const getPuzzleType = (r,c,num,board) => {
        outer : for(let i = 0 ; i < 12 ; i++){
            for(let d = 0 ; d < 4 ; d++){
                const [nR,nC] = [r+pR[i][d],c+pC[i][d]]
                if(!isCanGo(nR,nC)||board[nR][nC]!==num) continue outer
            }
            return i
        }
    }
    //해당번호의 타일이 어느 타입인지 추출
    const puzzleTypeMap = new Map()
    
    const visited = Array(201).fill(false) //시작점을 기준으로 타입을 검증함
    for(let i = 0 ; i < length ; i++){
        for(let j = 0 ; j < length ; j++){
            const num = board[i][j]
            if(!num||visited[num]) continue
            visited[num] = true
            const type = getPuzzleType(i,j,num,board)
            puzzleTypeMap.set(num,[i,j,type])
        }
    }
    
    //지울 가능성이 있는 타일들을 저장
    let curAbleMap = new Map()
    for (const [num,[r,c,type]] of puzzleTypeMap){
        if(!isAblePuzzle[type]) continue
        curAbleMap.set(num,[r,c,type])
    }
    //해당 퍼즐을 지울 수 있는 상태인지
    const isCanDeletePuzzle = (r,c,type,num,board) => {
        for(let d = 0 ; d < deleteR[type].length ; d++){
            const [nR,nC] = [r+deleteR[type][d],c+deleteC[type][d]]
            for(let i = 0 ; i <= nR ; i++){
                if(board[i][nC]!==0) return false
            }
        }
        return true
    }
    //실제로 보드에서 퍼즐을 지움
    const deletePuzzle = (r,c,type,board) => {
        for (let d = 0 ; d < 4 ; d++){
            const [nR,nC] = [r + pR[type][d],c + pC[type][d]]
            board[nR][nC] = 0
        }
    }
    
    const startSize = curAbleMap.size
    while(1){
        const curSize = curAbleMap.size
        for(const [num,[r,c,type]] of curAbleMap){
        if(isCanDeletePuzzle(r,c,type,num,board)) {
            deletePuzzle(r,c,type,board)
            curAbleMap.delete(num)
            }
        }
        if(curSize===curAbleMap.size) break
    }
    return startSize - curAbleMap.size
}