와이유스토리

[시뮬레이션] 프로그래머스 퍼즐 조각 채우기 C++ 본문

코딩테스트/시뮬레이션

[시뮬레이션] 프로그래머스 퍼즐 조각 채우기 C++

유(YOO) 2023. 3. 28. 21:59

 

https://school.programmers.co.kr/learn/courses/30/lessons/84021

#include <vector>
#include <queue>

using namespace std;

int N, answer;
int dx[4] = {1, 0, -1, 0}; // 우하좌상
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> Board, Table;

bool check(int bx, int by, int tx, int ty, int k) { // k 회전 차이
    vector<vector<int>> B = Board;
    vector<vector<int>> T = Table;

    int cnt = 0;

    queue<vector<int>> q;
    q.push({bx, by, tx, ty});
    while(!q.empty()) {
        vector<int> v = q.front();
        q.pop();

        if (((v[2] < 0) || (v[3] < 0) || (v[2] >= N) || (v[3] >= N)) && ((v[0] < 0) || (v[1] < 0) || (v[0] >= N) || (v[1] >= N))) continue; // for문 바깥
        if ((v[2] < 0) || (v[3] < 0) || (v[2] >= N) || (v[3] >= N)) { // 경계 조심
            if (B[v[1]][v[0]] == 0) return false; // (B, T) = (0, 0) 퍼즐 칸 끼우기 불가능
            else continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인 안 해도 됨
        }
        if ((v[0] < 0) || (v[1] < 0) || (v[0] >= N) || (v[1] >= N)) {
            if (T[v[3]][v[2]] == 1) return false; // (B, T) = (1, 1) 퍼즐 칸 끼우기 불가능
            else continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인 안 해도 됨
        }

        if ((B[v[1]][v[0]] == 1) && (T[v[3]][v[2]] == 0)) continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인X
        if ((B[v[1]][v[0]] == 0) && (T[v[3]][v[2]] == 1)) { // (B, T) = (0, 1) 퍼즐 칸 끼우기 가능
            B[v[1]][v[0]] = 1;
            T[v[3]][v[2]] = 0;
            cnt++;
        }
        else return false; // (B, T) = (0, 0) or (1, 1) 퍼즐 칸 끼우기 불가능

        for(int i=0; i<4; i++) q.push({v[0] + dx[i], v[1] + dy[i], v[2] + dx[(i+k)%4], v[3] + dy[(i+k)%4]});
    }
    
    answer += cnt; // 퍼즐 한 개 칸 개수
    Board = B; // 퍼즐 끼우기
    Table = T;
    
    return true;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    N = game_board.size();
    Board = game_board;
    Table = table;
    
    for(int i=0; i<N; i++) { // DFS, 백트래킹 필요없음, O(N^4)=50^4=6250000
        for(int j=0; j<N; j++) { // 퍼즐 선택(기준)
            if (Table[i][j] == 1) { 
                for(int p=0; p<N; p++) {
                    for(int q=0; q<N; q++) {
                        if (Board[p][q] == 0) { // 보드 확인(회전 시계 방향 90도, 180도, 270도)
                            for(int k=0; k<4; k++) { // 상우하좌, 좌상우하, 하좌상우, 우하좌상
                                if (check(q, p, j, i, k)) continue;
                            }
                        }
                    }
                }
            }
        }
    }

    return answer;
}

 

#include <vector>
#include <queue>

using namespace std;

int N, answer;
int bdx[4] = {1, 0, -1, 0}; // 우하좌상
int bdy[4] = {0, 1, 0, -1};
int tdx[4] = {1, 0, -1, 0};
int tdy[4] = {0, 1, 0, -1};
vector<vector<int>> Board, Table;

bool check(int bx, int by, int tx, int ty) {
    vector<vector<int>> B = Board;
    vector<vector<int>> T = Table;

    int cnt = 0;

    queue<vector<int>> q;
    q.push({bx, by, tx, ty});
    while(!q.empty()) {
        vector<int> v = q.front();
        q.pop();

        if (((v[2] < 0) || (v[3] < 0) || (v[2] >= N) || (v[3] >= N)) && ((v[0] < 0) || (v[1] < 0) || (v[0] >= N) || (v[1] >= N))) continue; // for문 바깥
        if ((v[2] < 0) || (v[3] < 0) || (v[2] >= N) || (v[3] >= N)) {
            if (B[v[1]][v[0]] == 0) return false; // (B, T) = (0, 0) 퍼즐 칸 끼우기 불가능
            else continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인X
        }
        if ((v[0] < 0) || (v[1] < 0) || (v[0] >= N) || (v[1] >= N)) {
            if (T[v[3]][v[2]] == 1) return false; // (B, T) = (1, 1) 퍼즐 칸 끼우기 불가능
            else continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인X
        }

        if ((B[v[1]][v[0]] == 1) && (T[v[3]][v[2]] == 0)) continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인X
        if ((B[v[1]][v[0]] == 0) && (T[v[3]][v[2]] == 1)) { // (B, T) = (0, 1) 퍼즐 칸 끼우기 가능
            B[v[1]][v[0]] = 1;
            T[v[3]][v[2]] = 0;
            cnt++;
        }
        else return false; // (B, T) = (0, 0) or (1, 1) 퍼즐 칸 끼우기 불가능

        for(int i=0; i<4; i++) q.push({v[0] + bdx[i], v[1] + bdy[i], v[2] + tdx[i], v[3] + tdy[i]});
    }
    
    answer += cnt; // 퍼즐 한 개 칸 개수
    Board = B; // 퍼즐 끼우기
    Table = T;
    
    return true;
}

void rotate() { // 시계 방향
    int tempX = tdx[3];
    int tempY = tdy[3];
    for(int i=2; i>=0; i--) { // 뒤에서부터
        tdx[i+1] = tdx[i];
        tdy[i+1] = tdy[i];
    }
    tdx[0] = tempX;
    tdy[0] = tempY;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    N = game_board.size();
    Board = game_board;
    Table = table;
    
    for(int i=0; i<N; i++) { // DFS, 백트래킹 필요없음, O(N^4)=50^4=6250000
        for(int j=0; j<N; j++) { // 퍼즐 선택(기준)
            if (Table[i][j] == 1) { 
                for(int p=0; p<N; p++) {
                    for(int q=0; q<N; q++) {
                        if (Board[p][q] == 0) { // 보드 확인(회전 시계 방향 90도, 180도, 270도)
                            for(int k=0; k<4; k++) {
                                rotate(); // 상우하좌, 좌상우하, 하좌상우, 우하좌상
                                if (check(q, p, j, i)) continue;
                            }
                        }
                    }
                }
            }
        }
    }

    return answer;
}
#include <vector>
#include <queue>

using namespace std;

int N, answer;
int bdx[4] = {1, 0, -1, 0}; // 우하좌상
int bdy[4] = {0, 1, 0, -1};
int tdx[4] = {0, -1, 0, 1}; // 하좌상우
int tdy[4] = {1, 0, -1, 0};
vector<vector<int>> Board, Table;

bool check(int tx, int ty, int bx, int by) {
    vector<vector<int>> B = Board;
    vector<vector<int>> T = Table;

    int cnt = 0;

    queue<vector<int>> q;
    q.push({bx, by, tx, ty});
    while(!q.empty()) {
        vector<int> v = q.front();
        q.pop();

        if (((v[2] < 0) || (v[3] < 0) || (v[2] >= N) || (v[3] >= N)) && ((v[0] < 0) || (v[1] < 0) || (v[0] >= N) || (v[1] >= N))) continue; // for문 바깥
        if ((v[2] < 0) || (v[3] < 0) || (v[2] >= N) || (v[3] >= N)) {
            if (B[v[1]][v[0]] == 0) return false; // (B, T) = (0, 0) 퍼즐 칸 끼우기 불가능
            else continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인X
        }
        if ((v[0] < 0) || (v[1] < 0) || (v[0] >= N) || (v[1] >= N)) {
            if (T[v[3]][v[2]] == 1) return false; // (B, T) = (1, 1) 퍼즐 칸 끼우기 불가능
            else continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인X
        }

        if ((B[v[1]][v[0]] == 1) && (T[v[3]][v[2]] == 0)) continue; // (B, T) = (1, 0) 퍼즐 칸 끼우기 확인X
        if ((B[v[1]][v[0]] == 0) && (T[v[3]][v[2]] == 1)) { // (B, T) = (0, 1) 퍼즐 칸 끼우기 가능
            B[v[1]][v[0]] = 1;
            T[v[3]][v[2]] = 0;
            cnt++;
        }
        else return false; // (B, T) = (0, 0) or (1, 1) 퍼즐 칸 끼우기 불가능

        for(int i=0; i<4; i++) q.push({v[0] + bdx[i], v[1] + bdy[i], v[2] + tdx[i], v[3] + tdy[i]});
    }
    
    answer += cnt; // 퍼즐 한 개 칸 개수
    Board = B; // 퍼즐 끼우기
    Table = T;
    
    return true;
}

void rotate() { // 시계 방향
    int tempX = tdx[3];
    int tempY = tdy[3];
    for(int i=2; i>=0; i--) { // 뒤에서부터
        tdx[i+1] = tdx[i];
        tdy[i+1] = tdy[i];
    }
    tdx[0] = tempX;
    tdy[0] = tempY;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    N = game_board.size();
    Board = game_board;
    Table = table;
    
    for(int i=0; i<N; i++) { // DFS, 백트래킹 필요없음, O(N^4)=50^4=6250000
        for(int j=0; j<N; j++) { // 퍼즐 선택(기준)
            if (Board[i][j] == 0) { 
                for(int p=0; p<N; p++) {
                    for(int q=0; q<N; q++) {
                        if (Table[p][q] == 1) { // 보드 확인(회전 시계 방향 90도, 180도, 270도)
                            rotate(); // 우하좌상
                            if (check(q, p, j, i)) continue;

                            rotate(); // 상우하좌
                            if (check(q, p, j, i)) continue;

                            rotate(); // 좌상우하
                            if (check(q, p, j, i)) continue;

                            rotate(); // 하좌상우
                            if (check(q, p, j, i)) continue;
                        }
                    }
                }
            }
        }
    }

    return answer;
}

'코딩테스트 > 시뮬레이션' 카테고리의 다른 글

[시뮬레이션] 백준 14890 경사로 C++  (0) 2023.09.04
[시뮬레이션(회전)] (CHECK) 백준 20057 마법사 상어와 토네이도 C++  (0) 2023.03.31
[시뮬레이션(회전)] (CHECK) 프로그래머스 자물쇠와 열쇠 C++  (0) 2023.02.19
[시뮬레이션] 프로그래머스 [1차] 프렌즈4블록 C++  (0) 2022.03.03
[시뮬레이션] 백준 20056 마법사 상어와 파이어볼 C++  (0) 2022.02.08
'코딩테스트/시뮬레이션' Related Articles more
Comments