[프로그래머스] 퍼즐 조각 채우기 / Javascript

문제주소 :https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차

---

<문제 설명>

문제 설명

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

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

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

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

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

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

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

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

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

---

제한사항

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

---

입출력 예

game_boardtableresult

[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]	[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]	14
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0

---

입출력 예 설명

입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

 

<풀이법>

▒ 한줄 개념: DFS, 매트릭스 회전 ▒ 

상반기 네이버 공채 문제 중 하나입니다. 핵심 개념은 다음과 같습니다.

1. table로부터 퍼즐 조각 추출하여 저장

2. game_board를 회전해가며 빈 부분들에 퍼즐 조각들을 끼워보고, 맞을 경우 해당 퍼즐 조각 삭제 및 보드 빈 공간 채움

 

자세한 풀이방법은 아래와 같습니다. 해당 번호는 코드내 주석 번호입니다.

 

<풀이방법>

1. table로 부터 퍼즐 조각 추출

2. game_board에서 값이 0인 부분(빈 부분) 확인

3. 모든 퍼즐에 대해 빈 부분이 일치하는지 확인

  3-1. 퍼즐의 사이즈와 빈 부분의 사이즈가 동일한지 확인

  3-2. 퍼즐의 모양이 빈 부분의 모양과 동일한지 확인

  3-3. 3-1, 3-2가 모두 만족할 경우 사용된 퍼즐 삭제 및 퍼즐이 들어간 부분 값 변경(1로 변경), answer값 증가

4. game_board 회전

 

<코드(Javascript)>

let inBound;

// main
function solution(game_board, table) {
    let answer = 0;
    const length = game_board.length;
    inBound = isValueInBound(length);
    
    const puzzles = []; // 1
    for(let r = 0; r < length; r++){ 
        for(let c = 0; c < length; c++){
            if(table[r][c]){
                puzzles.push(getPieces(table, r, c, 0, 0));
            }
        }
    }
    
    for(let rotate = 0; rotate < 4; rotate++){
        for(let r = 0; r < length; r++){
            for(let c = 0; c < length; c++){
                if(!game_board[r][c]){ // 2
                    for(let i = 0; i < puzzles.length; i++){ // 3
                        const puzzle = puzzles[i];
                        const emptySize = getEmptySize(game_board, r, c); // 3-1
                        if(emptySize !== puzzle.length){
                            continue;
                        }
                        const check = checkPuzzleFit(game_board, puzzle, r, c); // 3-2
                        if(check){ // 3-3
                            puzzles.splice(i, 1);
                            updateBoard(game_board, puzzle, r, c);
                            answer += puzzle.length;
                            break;
                        }
                    }
                }
            }
        }
        game_board = rotateMatrix(game_board);
    }
    return answer;
}

// 퍼즐이 해당 위치에 맞는지 확인
const checkPuzzleFit = (board, puzzle, r, c) => 
    puzzle.every(piece => {
        const {row, col} = piece;
        return inBound(r+row) && inBound(c+col) && board[r + row][c + col] === 0;
    })

// 보드 내 퍼즐이 채워진 부분 값 변경 
const updateBoard = (board, puzzle, r, c) => {
    puzzle.map(piece => {
        const {row, col} = piece;
        board[r+row][c+col] = 1;
    })
}

// 해당 값이 보드의 바운더리 안에 있는지 확인
const isValueInBound = len => val => val >= 0 && val < len;

// table에서 퍼즐 추출
const getPieces = (table, r, c, r_off, c_off) => {
    const len = table.length;
    table[r][c] = 0;
    const pieces = [{
        row: r_off, col: c_off
    }]
    if(inBound(r+1) && table[r+1][c]){
        pieces.push(...getPieces(table, r+1, c, r_off+1, c_off));
    }
    if(inBound(r-1) && table[r-1][c]){
        pieces.push(...getPieces(table, r-1, c, r_off-1, c_off));
    }
    if(inBound(c+1) && table[r][c+1]){
        pieces.push(...getPieces(table, r, c+1, r_off, c_off+1));
    }
    if(inBound(c-1) && table[r][c-1]){
        pieces.push(...getPieces(table, r, c-1, r_off, c_off-1));
    }
    return pieces;
}

// 해당 빈 공간의 크기 측정
const getEmptySize = (board, r, c, visited = []) => {
    visited.push({
        row: r, col: c
    });
    const isVisited = (row, col) => 
        visited.some(piece => piece.row === row && piece.col === col)
    
    let count = 1;
    if(!isVisited(r+1, c) && inBound(r+1) && !board[r+1][c]){
        count += getEmptySize(board, r+1, c, visited);
    }
    if(!isVisited(r-1, c) && inBound(r-1) && !board[r-1][c]){
        count += getEmptySize(board, r-1, c, visited);
    }
    if(!isVisited(r, c+1) && inBound(c+1) && !board[r][c+1]){
        count += getEmptySize(board, r, c+1, visited);
    }
    if(!isVisited(r, c-1) && inBound(c-1) && !board[r][c-1]){
        count += getEmptySize(board, r, c-1, visited);
    }
    return count;
}

// 매트릭스 90도 회전
const rotateMatrix = matrix => {
    const length = matrix.length;
    const newMatrix = createNewMatrix(length);
    for(let r = 0; r < length; r++){
        for(let c = 0; c < length; c++){
            newMatrix[c][length-1-r] = matrix[r][c];
        }
    }
    return newMatrix;
}

// 회전을 위한 새 메트릭스 생성
const createNewMatrix = length => {
    const newMatrix = new Array(length);
    for(let i = 0; i < length; i++){
        newMatrix[i] = new Array(length);
    }
    return newMatrix;
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest