프로그래머스 위클리챌린지 레벨3 문제이다
"table"에 있는 block들을 이용해서 "game_board"를 채웠을 때 가장 많이 채울 수 있는 칸의 수를 구하는 문제이다.
이 문제가 레벨3이라니..라고 생각하며 풀었지만 다 풀고 풀이과정을 써보려 하니 3레벨이 맞는것같기도하다. 이 글을 보고있다면 해당문제를 풀다가 힌트가 필요하여 찾아보는 분들일 가능성이 클테니 개인적으로 했던 고민들 위주로 풀어보도록 하겠다.
<--자바스크립트 처음 배울 때 무작정 '자바스크립트로 테트리스 만들기'를 클론코딩 해본적이 있었는데 그때 테트리스 블록을 저장하던 방법으로 한번 블록을 저장해봐야겠다-->
그 방법이란 단순하게 블록을 구성하는 각 칸의 좌표를 찍는것인데
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 }