[JS] 카드 짝 맞추기

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

프로그래머스

 

 

 

 

 

문제 자체는 모든 경우의수를 탐색해보는 완전탐색 문제이다.

 

1. 현재 보드에서 열어볼 카드를 선택한다.

2. 카드의 짝을 찾는다.

3. 다시 열어볼 카드를 선택한다.

반복..

 

조금 생각할 부분은 일반적인 이동 외에 ctrl 이동이 있다는 점이다.

 

따라서 4방향으로 탐색하는것 이외에도 ctrl이동까지 생각을 해줘야 한다.

 

필자는 문제를 해결하기 위해서 크게 두가지 함수를 이용했다.

 

 

1. beforeOpenCard

   - 열어볼 카드를 선택하는 함수

   - 현재 상태의 보드에서 여러볼 수 있는 카드를 모두 한번씩 열어본 후, afterOpenCard로 넘겨준다.

 

 

2. afterOpenCard

   - 카드의 짝을 찾는 함수

   - 현재 상태 보드에서 target을 찾고 target을 찾았다면 카드가 지워졌다 생각하고 다시 beforeOpenCard로 넘겨준다.

 

 

 

위 역할을 하는 함수 2개를 사용하였다. 

 

함수가 펼쳐지는 모습을 간략하게 표현하자면 아래와 같다.

 

 

beforeOpenCard에서 현재 보드의 모든 카드를 한번씩 열어보면서 모든 경우의수를 탐사하게 된다.

afterOpenCard에서는 단순히 target의 짝을 찾는다.

 

이때 만약 짝이 없다면 탐색을 종료하고 그렇지 않다면 해당 보드 beforeOpenCard로 전달해 다시 모든 카드를 열어본다.

 

 

요약하자면 카드를 하나씩 열어보는 것은 DFS를 활용해서, 카드에서 카드로 움직이는 횟수를 구할때는 BFS를 활용하여 구하였다.

 

 

 

추상화가 나름 잘된거 같아 기분이 좋은 문제풀이였다.

function solution(board, r, c) {
    const dc = [1,0,-1,0]
    const dr = [0,1,0,-1]
    
    const isInBoard = (r,c) => {
        if(0<= r && r < 4 && 0<= c && c <4) return true
        return false
    }
    
    const ctrlMove = (d,r,c,board) => {
        do{
            r += dr[d]
            c += dc[d]
            
        }while(isInBoard(r,c) && board[r][c]===0)
        if(!isInBoard(r,c)) {
            r -= dr[d]
            c -= dc[d]
        }
        return [r,c]
    }
    
    const isClear =(board) => {
        for (let i = 0; i < 4 ; i++){
            for (let j=0;j<4;j++){
                if(board[i][j]!==0) return false
            }
        }
        return true
    }
    const copyBoard = (ary) => [0,0,0,0].map((_,i) => [...ary[i]])
    
    let ret = Infinity
    
    function beforeOpenCard (sR,sC,board,cnt) {
        const visited = [0,0,0,0].map(_ => [0,0,0,0])
        visited[sR][sC] = 1
        const que = [[sR,sC,cnt]]
        let queIdx = 0
        const startCnt = cnt
        
        while (queIdx < que.length){
            const [r,c,cnt] = que[queIdx]
            
            //앞면 오픈
            if(board[r][c]!==0){
                const nxBoard = copyBoard(board)
                const target = board[r][c]
                nxBoard[r][c] = 0
               
                afterOpenCard(r,c,nxBoard,target,cnt+1)
            }
            
            //ctrl움직임
            for (let d = 0 ; d < 4 ; d++){
                const [nR,nC] = ctrlMove(d,r,c,board)
                if(isInBoard(nR,nC) && !visited[nR][nC]){
                     visited[nR][nC] = 1
                     que.push([nR,nC,cnt+1])
                }
            }
            //일반 움직임
            for (let d = 0 ; d < 4 ; d++){
                const [nR,nC] = [r + dr[d],c + dc[d]]
                if(isInBoard(nR,nC) && !visited[nR][nC]){
                    visited[nR][nC] = 1
                    que.push([nR,nC,cnt+1])
                }
            }
            queIdx ++
        }
    }
    
    function afterOpenCard(sR,sC,board,target,cnt) {
        const visited = [0,0,0,0].map(_ => [0,0,0,0])
        visited[sR][sC] = 1
        const que = [[sR,sC,cnt]]
        let queIdx = 0
        const startCnt= cnt
        
        while(queIdx < que.length){
            const [r,c,cnt] = que[queIdx]
            
            //짝을 찾은 경우
            if(board[r][c]===target){
                const nxBoard = copyBoard(board)
                nxBoard[r][c] = 0
                if (isClear(nxBoard)) {
                    ret = Math.min(ret,cnt+1)
                    return
                }
                
                beforeOpenCard(r,c,nxBoard,cnt+1)
            }
            
            //ctrl움직임
            for (let d = 0 ; d < 4 ; d++){
                const [nR,nC] = ctrlMove(d,r,c,board)
                if(isInBoard(nR,nC) && !visited[nR][nC]){
                     visited[nR][nC] = 1
                     que.push([nR,nC,cnt+1])
                }
            }
            //일반 움직임
            for (let d = 0 ; d < 4 ; d++){
                const [nR,nC] = [r + dr[d],c + dc[d]]
                if(isInBoard(nR,nC) && !visited[nR][nC]){
                    visited[nR][nC] = 1
                    que.push([nR,nC,cnt+1])
                }
            }
            queIdx ++
        }
    }
  
   
    
    beforeOpenCard(r,c,copyBoard(board),0)
    return ret
    
}