[2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기] Javascript 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/72415?language=javascript

프로그래머스

알고리즘:  구현 +  비트마스킹  + bfs

분명 옛날에 풀었던 문제였는데 다시 푸느라 애먹었다... 최근 구현 + 그래프 탐색 문제를 많이 연습하고 싶었는데, 괜찮은 문제였던거 같다.

 

풀이

 

1. 한 턴이 지날수록 소모되는 cost는 똑같이 1이다. 즉, bfs를 통해 한 지점에서 행동할 수 있는 모든 경우의 수를 탐색한뒤, 모든 카드가 뒤집어 지면 함수를 종료하고 결과값을 return 하면 된다는 것이다.

 

2. 이제 한 지점에서 할수 있는 모든 행동을 해보며 bfs를 진행해 보자. 한 지점에서 행동할 수 있는 경우의 수는 최대 9개 이다. 상하좌우 방향키(4), cntr + 상하좌우 방향키(4) + enter(1)

하나씩 살펴보면,

 

-  상하좌우 이동은 (다음 칸으로 이동이 가능할때만 & 방문하지 않은 지점) 일시 이동해 준다. dx,dy 배열을 만든 후, for문을 이용해 코드량을 줄여줬다.

// 상하좌우
for(let i=0; i<4; i++) {
    const nx = x +dx[i]
    const ny = y +dy[i]

    if(nx < 4 && nx >=0 && ny <4 && ny>=0 && !visited[nx][ny][deleted][selected]) {
        visited[nx][ny][deleted][selected] = true
        nstack.push([nx,ny,deleted,selected,pare])
    }
}

- cntr 이동은 이동 (벽을 만날때 까지 ||  카드를 발견시) 을 해준뒤, 해당칸을 방문하지 않았을때만 행동해야 한다.

이를 while문을 통해 (맵 밖으로 이동시 해당위치 보정후 break || 카드 발견시 break)로 구현해 주었다..

// ctrl
for(let i=0; i<4; i++) {
    let nx = x
    let ny = y
    while(true) {
        nx += dx[i]
        ny += dy[i]

        if(nx<0) {
            nx = 0
            break
        } else if(nx === 4) {
            nx = 3
            break
        } else if(ny<0) {
            ny = 0
            break  
        } else if(ny === 4) {
            ny = 3
            break  
        } else if(board[nx][ny] > 0 && (deleted & (1<<board[nx][ny])) === 0) {
            break
        }
    }

    if(!visited[nx][ny][deleted][selected]) {
        visited[nx][ny][deleted][selected] = true
        nstack.push([nx,ny,deleted,selected,pare])
    }
}

 

 

- 이제 enter를 살펴보자. enter는 현재 위치에 카드가 있어야만 동작 할 수 있다. 또한 enter 후 해당 카드가 기존 카드와 일치하는지, 일치하지 않는지, 아니면 기존 enter 카드가 없는지 확인해 주면 된다. 또한 모든 카드를 뒤집었다면, 값을 return해 함수를 종료해주자.

// 지금 위치에 카드가 있다.
if(board[x][y] > 0 && (deleted & (1<<board[x][y])) === 0) {
    // 이미 enter를 했었음
    if(selected>0) {
        // enter 위치가 이전과 다름 -> 뒤집기
        if(selected !== cards[x][y]) {
            // 제거
            if(pare === board[x][y]) {
               deleted |= (1<<pare)
            }

            let delCnt = 0
            for(let i=1; i<7; i++) {
                if((deleted & (1<<i))>0) {
                   delCnt ++ 
                }
            }
            if(delCnt === goal) {
                return cnt
            }

            nstack.push([x,y,deleted,0,0])
        }
    }
    else {
        nstack.push([x,y,deleted,cards[x][y],board[x][y]])
    }
}

 

3. 이제 해결해야 할 중요한 문제가 남아 있다. 바로 무한 루프를 방지해주기 위해 visited 배열을 만들어 주는 것이다.

이 visited 배열을 만들기 위해 비트마스킹 기법을 사용했다. 사라진 카드들의 정보를 비트마스킹으로 기록해주어, 중복 방문을 방지해주었다.

또한 같은 카드들의 status들이라고 무작정 방문처리를 하면 안되는 이유가 있다. 카드를 선택하고 다를 카드를 선택하기 위해 한 지점을 재방문 할 수 있었기 때문이였다. 

이 부분을 해결하느라 꽤 골똘히 생각했는데,,, 각 카드의 독립적 정보를 저장하고 있는 cards 배열을 생성하기로 했다. 해당 cards 배열에서 현재 선택된 카드의 num 정보가 저장되어 있어, 현재 선택된 카드의 방문 기록을 별도로 처리 할 수 있게 되었다. 

또한 현재 카드는 같은 그림을 찾아야 하기 때문에, stack(혹은 q, js에서는 내장 queue가 없기에 array를 stack처럼 사용했다.)에 그림에 대한 정보를 별도로 저장해 주었다.

card 고유의 정보를 가지고 있는 배열 생성

let cards = Array.from({length:4},()=>Array(4).fill(0))
let cardNum = 1
for(let i=0; i<4; i++) {
    for(let j=0; j<4; j++) {
        if(board[i][j] >0) {
            goal +=1
            cards[i][j] = cardNum++
        }
    }
}

 

stack(queue) = [x,y,사라진카드,enter로 선택된 카드,해당 카드의 짝]

// x,y,사라진카드,enter로 선택된 카드,해당 카드의 짝
let stack = [[r,c,0,0,0]]
return bfs(stack,1);

 

visited[r위치][c위치][사라진 카드들][현재 enter로 선택된 카드]

// visited[r][c][사라진 카드들][현재 enter로 선택된 카드]
const visited = Array.from({length: 4},()=>Array.from({length: 4},()=> Array.from({length: (1<<7)},()=>Array.from({length: 13},()=> false))))

 

 

 

 

소스 코드

// ctrl 가장 가까운 카드 텔레포트, 없으면 마지막 칸
// 방향키 이동 -> 빈공간 없으면 이동 x
// visited + bfs (먼저 도착)
function solution(board, r, c) {
    let goal = 0;
    const dx = [0,1,0,-1]
    const dy = [1,0,-1,0]
    
    // command -> 방향키 4개 + cntl 4개 + enter: 9
    // visited[r][c][사라진 카드들][현재 enter로 선택된 카드]
    const visited = Array.from({length: 4},()=>Array.from({length: 4},()=> Array.from({length: (1<<7)},()=>Array.from({length: 13},()=> false))))
    
    let cards = Array.from({length:4},()=>Array(4).fill(0))
    let cardNum = 1
    for(let i=0; i<4; i++) {
        for(let j=0; j<4; j++) {
            if(board[i][j] >0) {
                goal +=1
                cards[i][j] = cardNum++
            }
        }
    }

    goal = Math.floor(goal/2)
    function bfs(stack,cnt) {
        let nstack = []
        while(stack.length>0) {
            let [x,y,deleted,selected,pare] = stack.pop() 
            // 상하좌우
            for(let i=0; i<4; i++) {
                const nx = x +dx[i]
                const ny = y +dy[i]
                
                if(nx < 4 && nx >=0 && ny <4 && ny>=0 && !visited[nx][ny][deleted][selected]) {
                    visited[nx][ny][deleted][selected] = true
                    nstack.push([nx,ny,deleted,selected,pare])
                }
            }
            
            // ctrl
            for(let i=0; i<4; i++) {
                let nx = x
                let ny = y
                while(true) {
                    nx += dx[i]
                    ny += dy[i]
                    
                    if(nx<0) {
                        nx = 0
                        break
                    } else if(nx === 4) {
                        nx = 3
                        break
                    } else if(ny<0) {
                        ny = 0
                        break  
                    } else if(ny === 4) {
                        ny = 3
                        break  
                    } else if(board[nx][ny] > 0 && (deleted & (1<<board[nx][ny])) === 0) {
                        break
                    }
                }
            
                if(!visited[nx][ny][deleted][selected]) {
                    visited[nx][ny][deleted][selected] = true
                    nstack.push([nx,ny,deleted,selected,pare])
                }
            }
        
            // enter
            // 지금 위치에 카드가 있다.
            if(board[x][y] > 0 && (deleted & (1<<board[x][y])) === 0) {
                // 이미 enter를 했었음
                if(selected>0) {
                    // enter 위치가 이전과 다름 -> 뒤집기
                    if(selected !== cards[x][y]) {
                        // 제거
                        if(pare === board[x][y]) {
                           deleted |= (1<<pare)
                        }
                        
                        let delCnt = 0
                        for(let i=1; i<7; i++) {
                            if((deleted & (1<<i))>0) {
                               delCnt ++ 
                            }
                        }
                        if(delCnt === goal) {
                            return cnt
                        }
                        
                        nstack.push([x,y,deleted,0,0])
                    }
                }
                else {
                    nstack.push([x,y,deleted,cards[x][y],board[x][y]])
                }
            } 
        }

        return bfs(nstack,cnt+1)
    }

    // x,y,사라진카드,enter로 선택된 카드,해당 카드의 짝
    let stack = [[r,c,0,0,0]]
    return bfs(stack,1);
}