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

[level 3] 퍼즐 조각 채우기 - 84021

문제 링크

성능 요약

메모리: 3.67 MB, 시간: 0.02 ms

구분

코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS）

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 03월 24일 21:51:20

문제 설명

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

---

입출력 예 설명

입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

풀이과정

게임보드의 빈 부분에 퍼즐 조각을 딱 맞게 끼울 수 있는 모든 셀 갯수를 리턴하면 된다.

로직은 다음과 같다.

1. 퍼즐 조각과 보드 조각을 나누어 각각 벡터에 저장한다.
2. 보드 조각을 순회하며 퍼즐 조각과 모양이 같으면 셀 갯수를 정답에 더한다.

조각 나누기

split_pieces 메서드에 해당하는 부분이다.

먼저 game_board와 table을 새 벡터에 각각 복사했다.
이들을 table2, game_board2라고 하자. 편의상 2벡터라고 부르겠다.

하나의 메서드 사용

보드와 퍼즐의 조각을 나누는 로직이 같으므로 split_pieces라는 하나의 메서드로 만들었다. 둘의 구분은 퍼즐 split인지 확인하는 bool 변수로 했다. 그리고 매개변수로 조건에 맞는 셀의 행, 열 인덱스와 원본 벡터, 2 벡터를 넣어주었다.

조건에 맞는 셀로부터 메서드 실행하기

game_board와 table의 크기가 같으므로 이중 반복문 안에서 같이 확인하면 된다. 2벡터의 해당 셀의 값이 조건에 맞는 경우 split_pieces를 실행하도록 한다. 원본이 아닌 2벡터의 값을 확인하는 이유는 다음에 설명할 2벡터의 갱신에서 나온다.
=> game_board2의 경우 조건에 맞는 값은 0, table2의 경우 조건에 맞는 값은 1

bfs하며 갱신하기

1. 2벡터의 갱신
   시작 셀을 큐에 넣고 bfs를 통해 조각을 순회한다. 한 번 방문했던 조각은 다시 방문해서는 안되므로, 큐에 넣고 2벡터의 셀 값을 조건에 맞지 않는 값으로 바꿔준다.
   => game_board2의 경우 0 -> 1, table2 의 경우 1 -> 0
   원본을 남겨둔 이유는 조각을 복사하는 용도로 사용하기 위함이다.

2. 조각 행, 열의 시작과 끝 갱신
   또한 'ㅏ' 모양과 같이 조각에 빈 부분이 존재하는 경우 빈 부분까지 복사를 해야하므로, 조각에 해당하는 행의 시작과 끝, 열의 시작과 끝 인덱스를 bfs 과정 안에서 갱신해준다.

조각 복사하여 저장하기

저장해둔 조각의 시작과 끝 인덱스를 통해서 원본 벡터를 순회하여 조각을 복사한다.
비교의 편의를 위해서 퍼즐 조각은 그대로 복사하여 puzzle_p 벡터에 저장하고, 보드 조각은 0,1을 반전하여 board_p 벡터에 저장한다.

조각 회전하기

이 문제에서 조각을 비교할 때 뒤집기는 불가능하지만 회전은 가능하다. 그렇기 때문에 조각을 회전하는 메서드를 만들었다. rotate_p에 해당하는 부분이다.

원본 조각 cur의 행 크기 r과, 열 크기 c을 저장한다.
그리고 회전된 조각을 저장할 벡터 ret를 선언할 때, 행 크기를 c로, 열 크기를 r로하여 선언한다.

회전본을 저장하는 코드는 다음과 같다.

 for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            ret[j][i] = cur[r - i - 1][j];
        }
    }

그림을 그려서 확인하면 코드를 짜기 수월하다.

조각 비교하기

compare_p와 comp_cnt 함수에 해당하는 부분이다.
compare_p 조각이 들어갈 수 있는지 확인하고 회전하여 가능한 경우 comp_cnt를 호출한다. comp_cnt가 리턴한 셀 갯수를 다시 리턴한다.
comp_cnt에서는 두 조각의 값들을 비교하고 셀의 갯수를 세서 리턴한다.

조각이 들어갈 수 있는가

먼저 퍼즐조각이 들어갈 수 있는지 확인한다.
보드조각의 행크기과 열크기를 br, bc로, 퍼즐조각의 행크기와 열크기를 pr, pc라고 하자.

1. 정사각형
   br == pr && bc == pc && br == bc 인 경우이다.
   정사각형일 때는 회전 횟수 0~3을 모두 확인한다.

2. 직사각형(회전하지 않았을 때 같음)
   br == pr && bc == pc && br != bc 인 경우이다.
   정사각형은 아니면서 회전하지 않았을 때 같다면, 회전 횟수 0과 2만 확인한다.

3. 직사각형(회전을 한 번 했을 때 같음)
   br != pr && br == pc && bc == pr 인 경우이다.
   회전을 1번 했을 때 같다면, 회전 횟수 1과 3만 확인한다.

4. 회전을 해도 크기가 같지 않음
   br != pr && (br != pc || bc != pr) 인 경우이다. 이 경우에는 비교가 불가능 하므로 0을 리턴한다.

셀 갯수 세기

조각이 들어갈 수 있는 경우 comp_cnt로 셀 갯수를 센다. 보드조각과 퍼즐조각을 비교하여 1인 경우만 세서 cnt에 저장한다. 만약 조각이 다르면 중간에 0을 리턴한다. 중간에 리턴되지 않는 경우에는 셀 갯수가 리턴된다.

이미 사용된 퍼즐조각 visit 처리하기

보드조각의 순회 안에서 퍼즐조각을 순회하여 비교를 진행하는데, 이미 사용된 퍼즐조각의 경우 다시 사용할 수 없으므로, cnt가 0이 아닐 때 visit 처리를 해준다. puzzle_p 크기의 bool 벡터를 선언하여 저장한다.

코드

#include <string>
#include <vector>
#include <queue>
#define X first
#define Y second

using namespace std;

vector<vector<int>> table2, game_board2;
vector<vector<vector<int>>> puzzle_p, board_p;
vector<bool> visit;
int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1};
int n;

void split_pieces(int a, int b, vector<vector<int>> &t, 
                  vector<vector<int>> &t2, 
                  bool is_pz){
    queue<pair<int,int>> q;
    q.push({a,b}); t2[a][b] = 0;

    int sr = a, er = a, sc = b, ec = b;

    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int x = cur.X, y = cur.Y;

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if(t2[nx][ny] != is_pz) continue;
            t2[nx][ny] = !is_pz; q.push({nx,ny});

            if(nx < sr) sr = nx;
            if(ny < sc) sc = ny;
            if(nx > er) er = nx;
            if(ny > ec) ec = ny;
        }
    }

    vector<vector<int>> v;

    for(int i = sr; i <= er; i++){
        vector<int> r;
        for(int j = sc; j <= ec; j++) {
            if(is_pz) r.push_back(t[i][j]);
            else r.push_back(!t[i][j]);
        }
        v.push_back(r);
    }
    if(is_pz) puzzle_p.push_back(v);
    else board_p.push_back(v);
}

vector<vector<int>> rotate_p(vector<vector<int>> cur){
    int r = cur.size(), c = cur[0].size();
    vector<vector<int>> ret(c, vector<int>(r, 0));
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            ret[j][i] = cur[r - i - 1][j];
        }
    }
    return ret;
}

int comp_cnt(int &br, int &bc, vector<vector<int>> &bp, vector<vector<int>> &pp){
    int cnt = 0;
    for(int i = 0; i < br; i++){
        for(int j = 0; j < bc; j++) {
            if(bp[i][j] != pp[i][j]) return 0;
            if(bp[i][j] == 1) cnt++;
        }   
    }
    return cnt;
}

int compare_p(vector<vector<int>> &bp, vector<vector<int>> pp, int idx){
    int br = bp.size(), bc = bp[0].size();
    int pr = pp.size(), pc = pp[0].size(), cnt = 0;

    if(br == pr && bc == pc){
        if(br == bc) { // 정사각형 -> 0 ~ 3 회전 비교
            for(int i = 0; i < 4; i++) {
                if(i > 0) pp = rotate_p(pp);
                cnt = comp_cnt(br, bc, bp, pp);
                if(cnt) {
                    visit[idx] = 1;
                    return cnt;
                }
            }
        } else {
            cnt = comp_cnt(br, bc, bp, pp); // 0 회전
            if(cnt) {
                visit[idx] = 1;
                return cnt;
            }
            pp = rotate_p(rotate_p(pp)); // 2 회전
            cnt = comp_cnt(br, bc, bp, pp);
        }
    } else {
        if(br != pc || bc != pr) return 0; // 1 회전 해도 안됨 -> 불가능
        pp = rotate_p(pp); // 1 회전
        cnt = comp_cnt(br, bc, bp, pp);
        if(cnt) {
            visit[idx] = 1;
            return cnt;
        }
        pp = rotate_p(rotate_p(pp)); // 3 회전
        cnt = comp_cnt(br, bc, bp, pp);
    }

    if(cnt) visit[idx] = 1;
    return cnt;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    n = table.size();
    game_board2 = game_board;
    table2 = table;
    int answer = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(table2[i][j]) split_pieces(i, j, table, table2, 1);
            if(!game_board2[i][j]) split_pieces(i, j, game_board, game_board2, 0);
        } 
    }    

    visit.resize(puzzle_p.size(), 0);
    int idx = 0;

    for(auto bp : board_p){
        idx = 0;
        for(auto pp : puzzle_p){
            if(visit[idx++]) continue;
            int tmp = compare_p(bp, pp, idx-1);
            answer += tmp;
            if(tmp) break;
        }
    }


    return answer;
}

---

코드가 너무 길다... 최대한 간결하게 짜려고 했는데 이게 맞는 건지?
그래도 보드 크기가 최대 50이라서 시간복잡도에서 걸리지는 않았다.
만약에 코테에서 이런 문제가 나오면 시간 안에 짤 수 있으려나 그런 의문이 드는 문제였다.
알고리즘 자체는 단순히 bfs를 사용하는 거라 어렵지 않은데 부가적인 부분이 너무 길다.