코딩 테스트 - 퍼즐 조각 채우기

퍼즐 조각 채우기

문제 링크 : 퍼즐 조각 채우기

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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_board	table	result
[[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

풀이 방법

• game_board에서 0인 값을 인접한 블록으로 묶어서 도형을 만들어 놓고, table에서 1인 값을 인접한 블록으로 묶어서 도형을 만들고 이를 비교해서 들어갈 수 있는지 확인하는 방법을 통해 문제를 풀었다.
• 먼저 x, y 값을 같이 관리하기 위해 Point라는 구조체를 선언했다. 다음으로 bfs를 통해 인접한 블록을 추출하고자 했는데, game_board에서는 0, table에서는 1인 값을 확인해야 되기 때문에 별도의 target 변수를 통해 확인해야 하는 값을 받아서 비교했다.

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 인접한 블록 추출하기
vector<Point> bfs(int start_x, int start_y, vector<vector<int>>& board, int target) {
    queue<Point> Q;
    vector<Point> block;
    Q.push({start_x, start_y});
    board[start_x][start_y] = -1;
    
    while(!Q.empty()){
        Point cur = Q.front(); Q.pop();
        block.push_back(cur);
        for(int dir = 0; dir < 4; ++dir){
            int temp_x = cur.x + dx[dir];
            int temp_y = cur.y + dy[dir];
            if(temp_x < 0 || temp_x >= n 
               || temp_y < 0 || temp_y >= n) continue;
            if(board[temp_x][temp_y] == target){
                Q.push({temp_x, temp_y});
                board[temp_x][temp_y] = -1;
            }
        }
    }
    
    return normalize(block);
}

• 해당하는 블록을 추출했을 경우에 각 좌표별로 추출되니 비교하기가 어려워서, 이를 (0,0)을 기준으로 정규화를 하기 위해서 block을 받아와서 가장 작은 값을 (0,0)으로 정규화하는 함수를 만들었다.

// 좌표 정규화
vector<Point> normalize(vector<Point>& block){
    int minX = 51, minY = 51;
    for(Point& p : block){
        minX = min(minX, p.x);
        minY = min(minY, p.y);
    }
    
    vector<Point> result;
    for(Point& p : block){
        result.push_back({p.x - minX, p.y - minY});
    }
    
    sort(result.begin(), result.end(), [](Point& a, Point& b){
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    });
    
    return result;
}

• 블록이 빈 공간에 들어갈 수 있을지 검사할 때, 블록을 회전하면서 들어갈 수 있는지 검사해야 되기 때문에 90도씩 시계방향으로 회전시키는 함수를 만들었다.

// 90도씩 블록 회전
vector<Point> rotate(vector<Point> block){
    vector<Point> result;
    for (Point& p : block){
        result.push_back({p.y, -p.x});
    }
    return normalize(result);
}

• 처음에 말했듯이 먼저 game_board의 빈 공간과 table의 퍼즐 도형을 추출했고, 빈 공간에 퍼즐 도형이 들어갈 수 있는지 검사하면서 들어갈 수 있다면 정답에 추가하는 식으로 문제를 해결했다.

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    n = game_board.size();
    vector<vector<Point>> empties, puzzles;
    
    // 빈 공간 및 퍼즐 block 추출
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(game_board[i][j] == 0){
                vector<Point> block = bfs(i, j, game_board, 0);
                empties.push_back(block);
            }
            
            if(table[i][j] == 1){
                vector<Point> block = bfs(i, j, table, 1);
                puzzles.push_back(block);
            }
        }
    }
    
    vector<bool> used(puzzles.size(), false);
    int answer = 0;
    
    // 빈칸마다 퍼즐 맞추기
    for(vector<Point>& empty : empties){
        for(int i = 0; i < puzzles.size(); ++i){
            if(used[i]) continue;
            
            vector<Point>& puzzle = puzzles[i];
            bool isOk = false;
            for(int r = 0; r < 4; ++r){
                if (empty == puzzle){
                    answer += empty.size();
                    used[i] = true;
                    isOk = true;
                    break;
                }
                puzzle = rotate(puzzle);
            }
            
            if(isOk) break;
        }
    }
    
    return answer;
}

-> 해당 문제 풀이는 블록 추출 단계에서는 bfs와 정규화를 거치기 때문에 bfs에서 O(N^2), 정규화에서 O(NlogN)의 시간복잡도를 가지기 때문에 O(N^2log(N^2))의 시간복잡도를 가진다고 볼 수 있고, 퍼즐을 맞추는 단계에서는 최악의 경우 O(N^4)의 시간복잡도를 가진다고 볼 수 있다. N은 최대 50이기 때문에 충분히 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    int x, y;
    
    bool operator==(const Point& Other) const{
        return (x == Other.x) && (y == Other.y);
    }
};

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n;

// 좌표 정규화
vector<Point> normalize(vector<Point>& block){
    int minX = 51, minY = 51;
    for(Point& p : block){
        minX = min(minX, p.x);
        minY = min(minY, p.y);
    }
    
    vector<Point> result;
    for(Point& p : block){
        result.push_back({p.x - minX, p.y - minY});
    }
    
    sort(result.begin(), result.end(), [](Point& a, Point& b){
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    });
    
    return result;
}

// 90도씩 블록 회전
vector<Point> rotate(vector<Point> block){
    vector<Point> result;
    for (Point& p : block){
        result.push_back({p.y, -p.x});
    }
    return normalize(result);
}

// 인접한 블록 추출하기
vector<Point> bfs(int start_x, int start_y, vector<vector<int>>& board, int target) {
    queue<Point> Q;
    vector<Point> block;
    Q.push({start_x, start_y});
    board[start_x][start_y] = -1;
    
    while(!Q.empty()){
        Point cur = Q.front(); Q.pop();
        block.push_back(cur);
        for(int dir = 0; dir < 4; ++dir){
            int temp_x = cur.x + dx[dir];
            int temp_y = cur.y + dy[dir];
            if(temp_x < 0 || temp_x >= n 
               || temp_y < 0 || temp_y >= n) continue;
            if(board[temp_x][temp_y] == target){
                Q.push({temp_x, temp_y});
                board[temp_x][temp_y] = -1;
            }
        }
    }
    
    return normalize(block);
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    n = game_board.size();
    vector<vector<Point>> empties, puzzles;
    
    // 빈 공간 및 퍼즐 block 추출
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(game_board[i][j] == 0){
                vector<Point> block = bfs(i, j, game_board, 0);
                empties.push_back(block);
            }
            
            if(table[i][j] == 1){
                vector<Point> block = bfs(i, j, table, 1);
                puzzles.push_back(block);
            }
        }
    }
    
    vector<bool> used(puzzles.size(), false);
    int answer = 0;
    
    // 빈칸마다 퍼즐 맞추기
    for(vector<Point>& empty : empties){
        for(int i = 0; i < puzzles.size(); ++i){
            if(used[i]) continue;
            
            vector<Point>& puzzle = puzzles[i];
            bool isOk = false;
            for(int r = 0; r < 4; ++r){
                if (empty == puzzle){
                    answer += empty.size();
                    used[i] = true;
                    isOk = true;
                    break;
                }
                puzzle = rotate(puzzle);
            }
            
            if(isOk) break;
        }
    }
    
    return answer;
}