[프로그래머스/Javascript] 퍼즐 조각 채우기 (위클리 챌린지 3주차)

프로그래머스 코딩테스트 퍼즐 조각 채우기 (위클리 챌린지 3주차)

Javascript

문제

> 프로그래머스 문제 바로가기

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

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

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

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

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

최대한 많은 조각을 채워 넣으면 총 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에는 반드시 하나 이상의 블록이 놓여 있습니다.

풀이

solution function

function solution(game_board, table) {
    let answer = 0;
    // spaces: 게임판의 빈 칸 리스트, puzzles: 테이블의 퍼즐 리스트
    let spaces = [], puzzles = [];
    
    for(let y = 0; y < table.length; y++) {
        for(let x = 0; x < table[0].length; x++) {
            // game_board의 칸이 빈 칸(0)일 경우
            if(game_board[y][x] === 0) {
                let space = [];
                dfs(game_board, x, y, space, 0);  // 해당 칸과 이어지는 칸 탐색
                space = rearrange(space);  // (0,0)에서 시작하는 모양으로 재정렬
                space = rotate(space);  // 어떤 방향이더라도 한 방향의 모양으로 변형
                spaces.push(space);
            }
            // table의 칸이 블록(1)일 경우
            if(table[y][x] === 1) {
                let puzzle = [];
                dfs(table, x, y, puzzle, 1);  // 해당 칸과 이어지는 칸 탐색
                puzzle = rearrange(puzzle);  // (0,0)에서 시작하는 모양으로 재정렬
                puzzle = rotate(puzzle);  // 어떤 방향이더라도 한 방향의 모양으로 변형
                puzzles.push(puzzle);
            }
        }
    }
    
    for(let space of spaces) {
        for(let i = 0; i < puzzles.length; i++) {
            if(JSON.stringify(space) === JSON.stringify(puzzles[i])) {
                answer += puzzles[i].length;
                puzzles = puzzles.map((p,idx) => idx === i ? [] : p);
                break;
            }
        }
    }
    
    return answer;
}

dfs function

// 이어지는 칸 탐색 -> 모형 완성
function dfs(table, x, y, list, find) {
             // 우, 좌, 하, 상
    const dx = [1, -1, 0, 0];
    const dy = [0, 0, 1, -1]
    const stack = [[x,y]];
    const len = table.length;
    list.push([x,y]);
    
    while(stack.length) {
        let [a, b] = stack.pop();
        let moveX, moveY;
        table[y][x] = -1;
    
        // 우, 좌, 하, 상 순으로 stack에 저장
        for(let i = 0; i < 4; i++) {
            moveX = a + dx[i];
            moveY = b + dy[i];
            
            // 이동한 좌표가 테이블에서 벗어나 있는 경우는 제외
            if(moveX < 0 || moveX >= len) continue;
            if(moveY < 0 || moveY >= len) continue;
            
            // 이동한 좌표의 값이 찾고자 하는 값과 일치하면 stack과 list에 push하고, 다녀갔다는 표시 (-1 처리)
            if(table[moveY][moveX] === find) {
                table[moveY][moveX] = -1;
                stack.push([moveX, moveY]);
                list.push([moveX, moveY]);
            }
        }
    }
}

rearrange function

// 블록 or 빈칸을 (0,0)으로 이동시켜 반환
function rearrange(list) {
    const minX = Math.min(...list.map(c => c[0]));
    const minY = Math.min(...list.map(c => c[1]));
    return list.map(c => [c[0]-minX, c[1]-minY]).sort();
}

rotate function

// 사방으로 회전 후 한 개의 값 반환
function rotate(list) {
    if(list.length === 1) return list;
    let result = [];
    let shape = list.map(l => l);
    let width = Math.max(...shape.map(s => s[1])) - Math.min(...shape.map(s => s[1]));
    let height = Math.max(...shape.map(s => s[0])) - Math.min(...shape.map(s => s[0]));
    let w;

    for(let i = 0; i < 4; i++) {
        let temp = rearrange(shape.map(c => [c[1], width - c[0]]));
        shape = temp;
        result.push(shape);
        w = width;
        width = height;
        height = w;
    }
    
    return result.sort()[0];
}

2021.08.22