프로그래머스_JS - 퍼즐 조각 채우기

nd098pkc·2022년 6월 9일
3

코딩테스트 준비

목록 보기
3/15

프로그래머스 위클리챌린지 레벨3 문제이다

문제

문제링크

"table"에 있는 block들을 이용해서 "game_board"를 채웠을 때 가장 많이 채울 수 있는 칸의 수를 구하는 문제이다.
이 문제가 레벨3이라니..라고 생각하며 풀었지만 다 풀고 풀이과정을 써보려 하니 3레벨이 맞는것같기도하다. 이 글을 보고있다면 해당문제를 풀다가 힌트가 필요하여 찾아보는 분들일 가능성이 클테니 개인적으로 했던 고민들 위주로 풀어보도록 하겠다.

풀이과정

<입력>

  1. 일부 칸이 비워져있는 게임판 "game_board" (n*n크기의 2차원 Array)
  2. 빈칸을 채울 퍼즐조각들이 제시된 "table" (n*n크기의 2차원 Array)

<핵심아이디어>

  1. 우선 여러 퍼즐조각을 모아서 빈칸을 채우는 경우는 배제되었고 이것이 그래도 이 문제를 그나마 레벨3으로 느낄 수 있게 해주는 조건이다.
    game_board의 빈칸 모양과 table의 퍼즐조각 모양을 비교해서 동일한 모양이 나오면 퍼즐조각의 크기만큼 count를 더해주는 방식이 가장 유효해보인다.
  2. 그렇다면 이제 가장 중요한 부분은 "퍼즐조각(블록)과 빈칸의 모양을 어떤 방식으로 저장할것인가"가 되겠다.
  3. 그리고 퍼즐조각은 뒤집을수는 없지만 회전시킬 수 있다고 한다. 회전한 모양의 블록도 구현할 수 있도록 해야한다.

<퍼즐조각 모양 저장하기>

<--자바스크립트 처음 배울 때 무작정 '자바스크립트로 테트리스 만들기'를 클론코딩 해본적이 있었는데 그때 테트리스 블록을 저장하던 방법으로 한번 블록을 저장해봐야겠다-->
그 방법이란 단순하게 블록을 구성하는 각 칸의 좌표를 찍는것인데

이런 모양이 있다면 블록의 좌표는 [[0,0],[0,1],[1,1],[2,1],[2,2]]가 되는것이다.

2차원 배열에서 블록의 좌표를 따는 방법은 BFS를 사용했는데 모든 블록의 좌표만 딸 수 있으면 어떤 방법이든 상관은 없을것같다.
하지만 2차원 배열에서 좌표를 탐색하는데 이만한 방법이 따로 있을까

일단 순서대로 각 칸들을 돌면서 시작점을 발견하면 시작점을 넣고 돌릴 함수를 만들어주면 된다.
function bfs(start(시작점), table(게임판), k(빈칸(0) or 블록(1)){

 // 여기서 k의 의미는 game_board에서는 0으로 된 빈칸의 좌표를 따야하고 table에서는 1로된 블럭의
    좌표를 따야해서 한 함수로 둘다 처리하기 위해 넣게 되었다. 

 let needVisit = start                //needVisit에서 shift로 꺼내갈것이기 때문에 
                                        start의 형식은 [x,y]가 아닌 [[x,y]]가 되어야한다.
                                        [x,y]로 할거면 let needVisit=[start]로 해두거나..
 let block = []                       //블록 좌표 담을 배열
 const dx = [0,0,1,-1]                //최단거리 찾기 할 때 자주 보던 스킬
 const dy = [1,-1,0,0]                //상하좌우 탐색할때 제일 편한 것 같다.

 while(needVisit.length>0){           //꺼낼것이 없을때까지       
     let [cx,cy]=needVisit.shift()    //현재좌표를 꺼내서
     block.push([cx,cy])              //일단 블록 좌표 찍어준다
     table[cx][cy] = k                //방문좌표 재방문 방지용 변경

     for(let i=0;i<4;i++){            //상하좌우로 가보겠다는 뜻
         let nx=cx+dx[i]              //새 x좌표
         let ny=cy+dy[i]              //새 y좌표
        
         if(nx<0||ny<0||nx>=table.length||ny>=table.length) continue; 
                                      // 좌표가 0보다 작거나 테이블 크기보다 크면 패스  
         else if(table[nx][ny]===k) continue;
                                      // 새 좌표의 칸이 원하는 칸이 아니면 패스
         else {
             needVisit.push([nx,ny])  // 원하는 칸이면 needVisit에 넣어주고 
             table[nx][ny]=k	      // 다시방문하지 않도록 값 변경 
         }
     }
 }
    return block                      // 블록을 리턴
}

시작점으로부터 이 함수를 거치고 나면 시작점에 연결된 모든 빈칸(table에서는 블록)의 좌표가 배열로 리턴되게 된다.
그런데 여기서 중대한 문제가 발생한다
위 그림과 같은 예제에서 빨간 테두리의 두 모형은 같은 모양의 블록이어서 비교했을 때 같은 값을 가지고있어야 하지만 bfs 함수로 해당 블록을 표현하면 game_board의 도형은 [[0,2],[0,3],[1,3],[2,3],[2,4]]로 나오고 table의 도형은 [[0,3],[0,4],[1,4],[2,4],[2,5]]가 된다. 모양은 같지만 절대좌표로 보면 차이가 나기 때문이다.

<블록 좌표 기준점 통일>

이 문제에서 도형의 모양만 중요하지 위치는 필요가 없기 때문에 도형들이 같은 기준선을 가지도록 당겨주는 함수를 구현할 필요가 있다. 그 기준을 여기서는 [0,0]으로 잡겠다.

위 그림과같이 x좌표와 y좌표의 최소값만큼 좌표를 감소시켜주면 같은 모양의 블록은 모두 같은 값을 갖게된다.
좌표의 순서도 일치시키기 위해 정렬도 해서 리턴해준다.

function moveBlock(block){                            //블록 좌표배열을 인자로받아서
    let minX = Math.min(...block.map(v=>v[0]))        //x좌표중 최소값
    let minY = Math.min(...block.map(v=>v[1]))        //y좌표중 최소값

    return block.map(v=>[v[0]-minX,v[1]-minY]).sort() //모든 좌표의 x와 y값에 각각의 최소값을 빼주고 정렬 
}

moveBlock 함수를 완성하고 bfs에서 블록을 리턴할때 moveBlock 함수를 거치도록 변경해주었다

function bfs(start(시작점), table(게임판), k(빈칸(0) or 블록(1)){
 -------------------중략---------------------------
 return block ==> return moveBlock(block)으로 변경 
}

<블록 회전>

회전시킨 블록도 포함하여 계산하므로 블록을 회전시키는 함수도 만들어야한다.

function rotate(block){
    let max = Math.max(...block.map(v=>Math.max(v[0],v[1])))
    let rotateBlock=block.map(v=>[max-v[1],v[0]])
  
    return moveBlock(rotateBlock)
}

여러가지 방법이 있겠지만 나는 블록을 포함하는 정사각형 격자가 있다고 가정하고, y=x축 대칭이동에 y축(혹은 x축) 대칭이동을 한번 더하여 회전하는 함수를 구현했다. 이 과정에서 블록이 x=0, y=0 벽에서 떨어질 수 있기 때문에 한번 더 기준선으로 옮겨주는 함수를 거쳐 반환하도록 했다.

<블록 비교하기>

여기까지 진행하고 나니 이제는 solution함수에서 bfs함수를 통해 game_board에서 빈칸모양, table에서 블록모양을 추출하고 모양을 서로 비교하는 일만 남았다.

function solution(game_board, table) {
    let blanks=[]                                      //빈칸모양들 저장할 배열
    let blocks=[]                                      //블록모양들 저장할 배열
 for(let i=0;i<game_board.length;i++){                 
     for(let j=0;j<game_board.length;j++){             //[i,j] 좌표로 game_board를 탐색하다가
         if(game_board[i][j]===0){                     //해당칸이 0(빈칸)이면
             blanks.push(dfs([[i,j]],game_board,1))    //빈칸저장소에 빈칸을 저장
         }
     }
 }
    for(let i=0;i<table.length;i++){ 
     for(let j=0;j<table.length;j++){                  //[i,j] 좌표로 table을 탐색하다가
         if(table[i][j]===1){                          //해당칸이 1(블록)이면  
             blocks.push(dfs([[i,j]],table,0))         //블록저장소에 블록을 저장
         }
     }
 }

여기까지 거치고 나면 blanks에는 모든 빈칸의 모양들이, blocks에는 모든 블록의 모양들이 저장되어있다.
계속해서

let answer=0                                               //정답 초기화
blocks.forEach((val)=>{                                    //모든 블록들을
    for(let i=0;i<blanks.length;i++){                      //빈칸들에 비교해본다
      let match=false                                      //매칭되면 true로 변경할 변수 
      for(let j=0;j<4;j++){                                //4번 돌리면 제자리니까 4번만
          val=rotate(val)                                  //블록 돌리고
      if(JSON.stringify(val)===JSON.stringify(blanks[i])){ //배열이니까 JSON.stringify 이용하여 비교
                                                           //만약 같다면
          blanks.splice(i,1)         //채운 빈칸은 삭제
          answer+= val.length        //지금 블록의 크기만큼 answer++
          match=true                 //매칭된 블록이니 지금 블록은 중단해달라는 신호보내기용
          break;                     //사용한 블럭이니 중단
         }
       }
       if(match) break;              //해당블록으로 매칭성공했으면 다음 빈칸으로 가지 말고 중단
   }
})
return answer                        //모든 블록 다 써보고 나면 답이 나온다

결과는?

처음 문제를 접했을 때는 풀 수 있을까.. 이런 문제가 3레벨이라니.. 싶었지만 풀어가는 재미도 있고 성취감도 있는 문제였다.

전체코드

function moveBlock(block){
    let minX = Math.min(...block.map(v=>v[0]))
    let minY = Math.min(...block.map(v=>v[1]))
   
    return block.map(v=>[v[0]-minX,v[1]-minY]).sort()
}

function rotate(block){
    let max = Math.max(...block.map(v=>Math.max(v[0],v[1])))
    let rotateBlock=block.map(v=>[max-v[1],v[0]])
   
    return moveBlock(rotateBlock)
}

function bfs(start, table, k){
 const dx = [0,0,1,-1]
 const dy = [1,-1,0,0]
 let needVisit = start
 let block = []
 while(needVisit.length>0){
     let [cx,cy]=needVisit.shift()
     block.push([cx,cy])
     for(let i=0;i<4;i++){
         let nx=cx+dx[i]
         let ny=cy+dy[i]
       
         if(nx<0||ny<0||nx>=table.length||ny>=table.length) continue;
         else if(table[nx][ny]===k) continue;
         else {
             needVisit.push([nx,ny])
             table[nx][ny]=k
         }
     }
 }
    return moveBlock(block)
}

function solution(game_board, table) {
    let blanks=[]
    let blocks=[]
 for(let i=0;i<game_board.length;i++){
     for(let j=0;j<game_board.length;j++){
         if(game_board[i][j]===0){
             game_board[i][j]=1
             blanks.push(bfs([[i,j]],game_board,1))
         }
     }
 }
    for(let i=0;i<table.length;i++){
     for(let j=0;j<table.length;j++){
         if(table[i][j]===1){
             table[i][j]=0
             blocks.push(bfs([[i,j]],table,0))
         }
     }
 }
    let answer=0
    blocks.forEach((val)=>{
        for(let i=0;i<blanks.length;i++){
            let match=false
            for(let j=0;j<4;j++){
                val=rotate(val)
            if(JSON.stringify(val)===JSON.stringify(blanks[i])){
                blanks.splice(i,1)
                answer+= val.length
                match=true
                break;
            }
            }
            if(match) break;
        }
    })
return answer 
}
profile
늦게배운 코딩이 무섭다

0개의 댓글