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의 각 열 길이 = 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에는 반드시 하나 이상의 블록이 놓여 있습니다.

 

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

1) table 에서 퍼즐조각 얻기
2) game_table 에서 빈칸 얻기
3) 빈칸과 퍼즐조각 비교해서 채우기

 

1) table 에서 퍼즐조각 얻기

2) game_table 에서 빈칸 얻기

• DFS : 1인 곳을 발견하면(조각이 채워진 곳), 그 조각의 "상-하-좌-우" 가 채워져 있는지 확인
• puzzles, spaces 에 저장 : 이 때, "원점 이동"이 필요! (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