Lv_2. 3주차_퍼즐 조각 채우기

Lv_2. 3주차_퍼즐 조각 채우기

* Programmers _위클리 챌린지 문제입니다.

* 언어는 javascript 를 선택했습니다.

1. 문제

1) 퍼즐 조각 채우기

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

조각은 한 번에 하나씩 채워 넣습니다.

조각을 회전시킬 수 있습니다.

조각을 뒤집을 수는 없습니다.

게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.

5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

2) 제한사항

3 ≤ game_board의 행 길이 ≤ 50

game_board의 행 길이 ≤ 50 game_board의 각 열 길이 = game_board의 행 길이 즉, 게임 보드는 정사각 격자 모양입니다. game_board의 모든 원소는 0 또는 1입니다. 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다. 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.

game_board의 행 길이 table의 행 길이 = game_board의 행 길이

game_board의 행 길이 table의 각 열 길이 = table의 행 길이 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다. table의 모든 원소는 0 또는 1입니다. 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다. 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.

table의 행 길이 game_board에는 반드시 하나 이상의 빈칸이 있습니다.

table에는 반드시 하나 이상의 블록이 놓여 있습니다.

2. 알고리즘! 생각해보자

1) table 에서 퍼즐조각 얻기

2) game_table 에서 빈칸 얻기

3) 빈칸과 퍼즐조각 비교해서 채우기

1) table 에서 퍼즐조각 얻기

2) game_table 에서 빈칸 얻기

DFS : 1인 곳을 발견하면(조각이 채워진 곳), 그 조각의 "상-하-좌-우" 가 채워져 있는지 확인

puzzles, spaces 에 저장 : 이 때, " 원점 이동 "이 필요! (3단계를 위해)

"이 필요! (3단계를 위해) getPuzzles(), moveOrigin() 으로 구현

3) 빈칸과 퍼즐조각 비교해서 채우기

각 퍼즐의 원본, 90도, 180도, 270도 회전본을 생성 (회전본도 원점 이동이 필요)

빈칸과 회전된 퍼즐조각을 비교

채울 수 있으면 => 빈칸은 채우고, 퍼즐조각은 삭제 & 채워진 퍼즐 수만큼 answer 증가

checkFill(), getRotatedPuzzles(), fillSpace() 로 구현

3. 해결 코드

function solution(game_board, table) { let answer = 0; const puzzles = []; const spaces = []; const getPuzzle = (table, x, y, cmpVal) => { const puzzleIdx = (cmpVal ? puzzles.length : spaces.length) - 1; table[x][y] = cmpVal ? 0 : 1; if(cmpVal) { puzzles[puzzleIdx][x][y] = 1; } else { spaces[puzzleIdx][x][y] = 0; } // left if(y-1 > -1 && table[x][y-1] === cmpVal) { getPuzzle(table, x, y-1, cmpVal); } // right if(y+1 < table[x].length && table[x][y+1] === cmpVal) { getPuzzle(table, x, y+1, cmpVal); } // top if(x-1 > -1 && table[x-1][y] === cmpVal) { getPuzzle(table, x-1, y, cmpVal); } // bottom if(x+1 < table.length && table[x+1][y] === cmpVal) { getPuzzle(table, x+1, y, cmpVal); } } const moveOrigin = (table, cmpVal) => { const tableIdx = table.length - 1; let rowOrigin = 51; let colOrigin = 51; // 이동할 칸 수 count table[tableIdx].forEach((row, rowIdx) => { row.forEach((col, colIdx) => { if(col === cmpVal) { rowOrigin = Math.min(rowOrigin, rowIdx); colOrigin = Math.min(colOrigin, colIdx); } }) }); // 이동 table[tableIdx].forEach((row, rowIdx) => { row.forEach((col, colIdx) => { if(col === cmpVal) { table[tableIdx][rowIdx][colIdx] = cmpVal ? 0 : 1; table[tableIdx][rowIdx-rowOrigin][colIdx-colOrigin] = cmpVal; } }) }); } const getRotatedPuzzles = (puzzle) => { const rotatedPuzzles = [puzzle]; for(const i of [1, 2, 3]) { rotatedPuzzles.push(Array(puzzle.length).fill(0).map(() => Array(puzzle[0].length).fill(0))); for(var row = 0; row < puzzle.length; row++) { rotatedPuzzles[i][row] = rotatedPuzzles[i-1].map(v => v[row]).reverse(); } moveOrigin(rotatedPuzzles, 1); } return rotatedPuzzles; } const checkFill = (space, puzzle) => { let isFill = false; const rotatedPuzzles = getRotatedPuzzles(puzzle); const spaceIdxs = []; space.forEach((row, rowIdx) => { row.forEach((col, colIdx) => { if(col === 0) { spaceIdxs.push([rowIdx, colIdx]); } }) }); for(let i = 0; i < rotatedPuzzles.length; i++) { isFill = true; for(let j = 0; j < spaceIdxs.length; j++) { if(!rotatedPuzzles[i][spaceIdxs[j][0]][spaceIdxs[j][1]]) { isFill = false; break; } } if(isFill) { break; } } return isFill; } const fillSpace = (spaceIdx, puzzleIdx) => { // space 채우기 all to 1 spaces[spaceIdx] = Array(game_board.length).fill(1).map(() => Array(game_board[0].length).fill(1)); // puzzle 비우기 all to 0 puzzles[puzzleIdx] = Array(table.length).fill(0).map(() => Array(table[0].length).fill(0)); } // 1. get puzzle table.forEach((row, rowIdx) => { row.forEach((col, colIdx) => { if(col == 1) { puzzles.push(Array(table.length).fill(0).map(() => Array(row.length).fill(0))); getPuzzle(table, rowIdx, colIdx, 1); moveOrigin(puzzles, 1); } }); }); // 2. get empty space game_board.forEach((row, rowIdx) => { row.forEach((col, colIdx) => { if(col == 0) { spaces.push(Array(game_board.length).fill(1).map(() => Array(row.length).fill(1))); getPuzzle(game_board, rowIdx, colIdx, 0); moveOrigin(spaces, 0); } }); }); // console.log(spaces) // console.log(puzzles) // 3. fill the empty space spaces.forEach((space, spaceIdx) => { puzzles.forEach((puzzle, puzzleIdx) => { const spaceCnt = spaces[spaceIdx].reduce((acc, cur)=> acc + (cur.filter(v => v === 0).length), 0); const puzzleCnt = puzzles[puzzleIdx].reduce((acc, cur)=> acc + (cur.filter(v => v === 1).length), 0); // 개수가 동일한 경우, fill 가능성 있으므로 확인 if(spaceCnt === puzzleCnt) { if(checkFill(space, puzzle)) { fillSpace(spaceIdx, puzzleIdx); answer += puzzleCnt; } } }); }) return answer; }

4. 문제해결 능력 UP! 되짚어보기

다른 코드를 읽을 여력이 없었습니다...

5. References

from http://dongurami0502.tistory.com/30 by ccl(A) rewrite - 2021-11-13 02:28:14