프로그래머스-퍼즐 조각 채우기

문제 링크

1. 문제 접근 과정🧐

문제를 잘게 쪼개서 생각해야 한다!
1. 게임 보드에서 빈칸 모음 리스트를 BFS/DFS로 탐색
2. 테이블의 퍼즐 조각 모음 리스트를 BFS/DFS로 탐색
3. 각 리스트를 0,0을 기준으로 정규화->이는 좌표가 달라도 빈칸에 들어가는지 확인하기 위한 작업
4. 각 퍼즐 조각과 빈칸의 크기가 다르거나 이미 사용했던 조각이면 continue
5. 처음 모양부터 90도 회전을 4번하여 모양이 같으면 answer에 크기를 더하고 다음 빈칸으로 넘어감
6. 빈칸 리스트를 모두 탐색하면 해결

2. 시행착오🤯

• 빈칸 모음을 찾는 과정까지 해결하고 그 다음 과정의 감이 안잡혀 해결하지 못했다.
  • gpt를 활용하여 각 스텝 별로 접근하는 힌트를 얻었다.

3. 개선한 코드😄

• 'BFS/DFS -> 정규화 -> 빈칸에 맞는지 -> 회전' 이렇게 4개의 스텝으로 차근차근 해결하면 된다.
  
• 정답 코드

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

using namespace std;

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

vector<pair<int, int>> bfs(vector<vector<int>> &v, int sx, int sy, vector<vector<bool>> &visited, int target){
    vector<pair<int, int>> result;
    queue<pair<int, int>> q;
    q.push({sx, sy});
    visited[sx][sy] = true;
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        result.push_back({x, y});
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= v.size() || ny < 0 || ny >= v[0].size()) continue;
            if(v[nx][ny] == target && !visited[nx][ny]){
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return result;
}

void normalizePiece(vector<pair<int,int>>& piece) {
    int minX = INT_MAX, minY = INT_MAX;
    for (auto &p : piece) {
        minX = min(minX, p.first);
        minY = min(minY, p.second);
    }
    for (auto &p : piece) {
        p.first  -= minX;
        p.second -= minY;
    }
    sort(piece.begin(), piece.end());
}

vector<pair<int,int>> rotate90(vector<pair<int,int>> &piece) {
    vector<pair<int,int>> out;
    out.reserve(piece.size());
    for (auto p : piece) out.push_back({p.second, -p.first});
    normalizePiece(out);
    return out;
}

bool Fit(vector<pair<int, int>> &hole, vector<pair<int, int>> &piece){
    auto cur = piece;
    for(int i = 0; i < 4; i++){
        if(cur == hole) return true;
        cur = rotate90(cur);
    }
    return false;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0;
    vector<vector<bool>> visited1(game_board.size(), vector<bool>(game_board.size(), false));
    vector<vector<pair<int, int>>> game_empty;
    for(int i = 0; i < game_board.size(); i++){
        for(int j = 0; j < game_board[i].size(); j++){
            if(game_board[i][j] == 0 && !visited1[i][j]){
                game_empty.push_back(bfs(game_board, i, j, visited1, 0));
            }
        }
    }
    vector<vector<bool>> visited2(table.size(), vector<bool>(table.size(), false));
    vector<vector<pair<int, int>>> table_parts;
     for(int i = 0; i < table.size(); i++){
        for(int j = 0; j < table[i].size(); j++){
            if(table[i][j] == 1 && !visited2[i][j]){
                table_parts.push_back(bfs(table, i, j, visited2, 1));
            }
        }
    }
    for(auto &v : game_empty) normalizePiece(v);
    for(auto &v : table_parts) normalizePiece(v);
    vector<bool> used(table_parts.size(), false);
    for(auto &v : game_empty){
        for(int i = 0; i < table_parts.size(); i++){
            if(v.size() != table_parts[i].size() || used[i]) continue;
            if(Fit(v, table_parts[i])){
                used[i] = true;
                answer += v.size();
                break;
            }
        }
    }
    return answer;
}

4. 회고💭

• 이 문제는 생각해야 할 부분이 많아 복잡했다.
  • 문제를 잘게 쪼개서 각 단계 별로 차례로 풀면 해결할 수 있다.
  • 대문제를 소문제로 나누는 요령이 필요하겠다!