[C++] 프로그래머스 Level 3 - 퍼즐 조각 채우기

---

문제 이해 단계

0과 1로만 이루어진 2개의 서로 다른 2차원 맵이 주어진다.

왼쪽 맵은 0일 때 있는 퍼즐이 있는 것, 오른쪽 맵은 1일 때 퍼즐이 있는 것이다.
왼쪽 맵의 빈칸에 오른쪽 퍼즐을 끼우는데 딱 맞는 퍼즐만 끼울 수 있다.

이때 중요한 것은 퍼즐을 회전해서 끼울 수 있다는 것이다.
이러한 조건일 때 최대한 많은 퍼즐을 끼웠을 때 총퍼즐의 칸 수를 구하는 문제이다.

 

---

문제 접근 단계

일단 해당 문제의 유형부터 유추해 보자면
0과 1로만 이루어진 2차원 맵이 주어진 점,

그리고 퍼즐을 알아내야 하는 점을 보면
곧바로 그래프 탐색을 포함한 문제라는 것을 유추할 수 있다.

DFS나 DFS 중 하나로 풀면 될 것 같은데 
딱히 경로 자체는 그렇게 중요한 점이 아닌 것 같아서, 두 개 중 아무거나 상관없을 것 같다.
그래서 그냥 구현이 편한 BFS를 사용하기로 했다.

이 문제에서 가장 문제 되는 점은 퍼즐이 회전가능하다는 점이다.

회전이 가능하다는 뜻은 좌표상으로 생각할 때, 회전 할 때마다 좌표가 바뀐다는 것이다.
또한 애초부터 왼쪽과 오른쪽 맵의 배열이 다르기 때문에 좌표적으로도 기준이 없다.

 

퍼즐 기준 좌표 정하기

그래서 나는 어떻게 할까 고민하다가,
모든 퍼즐의 좌표를 (0,0)을 시작점으로 변환하였다.

이렇게 두 퍼즐의 시작점을 동일하게 하면
두 퍼즐의 좌표를 비교해서 두 퍼즐이 동일한 것인지 검사할 수 있다.

해당 변환 방식을 사용하기 위해 퍼즐을 둘러싼 사각형 전체를 잘라 
왼쪽 대각선 모서리 부분을 (0,0)에 맞추어 모두 표준화한다.

아래 그림처럼 말이다.

연두색 퍼즐의 빨간색 테두리를 보면
퍼즐이 없는 부분 또한 포함된 것을 볼 수 있다.

이런 식으로 사각형으로 자르고,
(0,0)과 가장 가까운 왼쪽 모서리 좌표를 (0,0)으로 변환하여
다른 좌표들도 그에 상응하여 변환한다.

이렇게 (0,0)으로 기준좌표로 맞춰줌으로써,
퍼즐들끼리의 좌표 비교를 통한 같음 유무를 판단할 수 있다.

하지만 퍼즐은 회전이 가능하다. 회전을 했을 때의 퍼즐의 좌표를 알아야 한다.

 

회전했을 때의 퍼즐 좌표

회전은 총 90도씩 4번 돌리는 것이 가능하다.
이때의 회전하는 퍼즐의 좌표를 구하는 것이 관건이다.

여러 블로그를 찾아보니, 내적 공식이나 여러 가지 수학 공식을 이용하여
퍼즐을 90도 돌렸을 때 직접적으로 좌표를 구하는 방식들이 많았다.

나는 이러한 공식을 몰랐을뿐더러, 수학에 약하다..
게다가 뭔가 알고리즘 문제를수학 공식에 의존해서 풀고 싶진 않다.

왜냐하면 내가 이 문제를 논리적으로 이해한 것이 아니라
그냥 공식을 이용해서 알아낸 것뿐이니까.

공식을 활용해서 풀면 알고리즘 공부에 큰 도움이 안 될 것 같았다.
그래서 다른 방법을 생각해 보았다.

그래서 내가 생각한 방법은 그냥 퍼즐 각각을 돌릴 필요 없이
보드판 자체를 90도씩 돌리자였다.

보드판을 90씩 돌리는 것을 그림으로 생각해 보자.

맨 윗 열을 주황색으로 표시하고,
시계방향으로 90도 돌린다고 생각하면 위에 그림처럼 될 것이다.

이를 반복문을 통해 구현한다고 생각하고
단계별로 생각하면 NxN 맵이 있다고 가정하자.

또한 i번째 행(가로)에 있는 좌표는 오름차순으로 N-i번째에 있는 열에 있는 좌표로 1:1 대응된다.

그림을 통해 보면 편하다.

위와 같은 방식으로 된다는 것이다.

90도 돌아간 퍼즐을 보면 해당 방식이
퍼즐을 올바르게 돌리는 방식이라는 것을 알 수 있다.

이러면 이제 답을 구할 수 있다. 알고리즘을 정리해 보자면 다음과 같다.

1. BFS를 통해 퍼즐 맵에서
각각의 퍼즐들의 좌표 정보를 가지고 있는 배열 뭉치를 가져온다.

2. 가져온 배열 뭉치의 기준 좌표를 (0,0)으로 통일하여
계산이 가능하도록 치환 작업을 해준다.

3. 보드 판의 빈 블록칸을 탐색하며
퍼즐과 칸이 맞는 부분이 있는지 확인한다.
이때 보드판의 빈 블록칸 또한 기준 좌표를 (0,0)으로 만들어주는 작업을 해준다.

4. 퍼즐과 칸이 맞는 부분이 있다면 퍼즐 리스트에서 해당 퍼즐을 없애고,
보드판에서 그 자리를 메꿔 더 이상 방문하지 못하도록 한다.

5. 90도를 돌려서 3~4번 과정을 반복한다.
해당 과정은 총 4번이 되거나, 퍼즐이 더 이상 없을 때까지 반복한다.

방식을 크게 정리하면 이런 식으로 되는데, 말로 설명하려다 보니까 많이 이상하다.
문제 구현 단계에서 코드를 보면서 자세히 설명하겠다.

 

---

문제 구현 단계

빈 공간, 퍼즐 좌표 정보 추출

struct Point{
    int x;
    int y;
};

vector<vector<bool> > check; // 방문 처리
vector<vector<Point> > puzzleList; // 퍼즐을 담는 리스트
vector<vector<Point> > emptyList; // 빈 공간을 담는 리스트

// 빈공간, 퍼즐 추출하기
// select를 통해 보드판, 퍼즐판 구분
vector<Point> getPuzzle(int sx,int sy,vector<vector<bool>> select){
    int dx[] = {0,0,-1,1};
    int dy[] = {-1,1,0,0};
    
    queue<Point> q;
    vector<Point> list;
    check[sx][sy] = true;
    Point p = {sx,sy};
    q.push(p);
    list.push_back(p);


    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= select.size() || ny >= select.size() 
            || check[nx][ny] || !select[nx][ny]) continue;
            check[nx][ny] = true;
            Point np = {nx,ny};
            q.push(np);
            list.push_back(np);
        }
    }
    return list;
}

공간 좌표를 추출하기 위한 BFS를 돌리는 함수이다.

공간좌표 (x, y)를 위해 Point라는 임의의 구조체를 만들어주어 사용했다.

BFS 함수의 특징적인 것을 살펴보면, 인자 중에 select를 이용하여 
해당 BFS가 퍼즐을 위한 것인지,빈 공간을 위한 것인지 구분한다.

그리고 전역변수로 설정해 둔 puzzleList 안에는 vector <Point>라는 벡터가 list로 들어간다.
즉 공간좌표 뭉치가 또 뭉치로 들어간다는 소리이다.

해당 BFS는 해당 퍼즐이 가지고 있는 블록의 좌표들을 모두 모아 반환한다.

 

좌표 통일하고 비교 판단하기

// (0,0)으로 리포지션 시키는 함수
vector<Point> rePos(vector<Point> p){
    int minX = p[0].x;
    int minY = p[0].y;

    for(int i = 1; i < p.size(); i++){
        minX = min(minX,p[i].x);
        minY = min(minY,p[i].y);
    }

    for(int i = 0; i < p.size(); i++){
        p[i].x -= minX;
        p[i].y -= minY;
    }
    return p;

}
// 두 퍼즐이 일치하는지 비교하는 함수
int comparePuzzle(vector<Point> a, vector<Point> b){
    int answer = 0;
    a = rePos(a);
    b = rePos(b);

    int count = 0;
    // 애초에 개수가 일치하지 않으면 틀림
    if(a.size() != b.size()) return 0;

    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < b.size(); j++){
            if(a[i].x == b[j].x && a[i].y == b[j].y){
                count++;
                break;
            }
        }
    }
    // 일치하는 좌표의 개수가 같을 때만 맞음
    if(count == a.size()) return a.size();
    else return 0;
}

(0,0)으로 좌표를 변환하는 것은 x값과 y값의 최솟값을 이용한다.

어차피 사각형으로 자르기 때문에 빈 공간이 생겨도 상관없다.
즉, 해당 퍼즐 블록 중에 x 값 y값 따로 최솟값을 찾아 그걸 기준으로 (0,0)으로 맞춘다.

다른 좌표도 딱 그만큼만 움직였을 거니까 그 값만 빼주면 된다.

comparePuzzle은 두 퍼즐을 비교하여 같은 것인지 확인하는 함수이다.

일단 두 함수를 위에 있는 rePos를 이용하여 정규화한다.
그리고 블록 하나씩(좌표 하나씩) 비교한다.

a와 b를 비교할 때 두 개가 동일한 조건은 당연히 일단 개수는 같아야 한다.
그리고 동일한 요소의 개수가 a 또는 b개수와 같아야 한다.(즉 전체여야 한다.)

이를 위해 count를 두어 a와 b의 좌표가 같을 때마다 count++를 해준다.

탐색이 끝난 후
count, 퍼즐의 개수, a (or) b개수
가 같을 때만 올바른 것이다.

90도 회전

// 90도 한번 돌리기
vector<vector<bool>> rotateOnce(vector<vector<bool> > origin){

    int c = origin.size(); // 행
    int r = origin.size(); // 열

    // 반환할 90도 돌아간 보드판
    vector<vector<bool>> board;
    vector<bool> row(r);

    for(int i = 0; i < c; i++) board.push_back(row);

    // 90도 돌리는 작업
    for(int i = 0; i < origin.size(); i++){
        for(int j = 0; j < origin[i].size(); j++){
            board[origin.size()-j-1][i] = origin[i][j];
        }
    }
    return board;
}

이중반복문을 이용해서 행과 열을 교환해 주었다.
이건 딱히 설명보단 직접 그려보는 것을 권장한다.

 

퍼즐을 이용해 보드판 채우기

// 다시 방문하지 않도록 빈 공간 메우기
vector<vector<bool>> fillBoard(vector<Point> p, vector<vector<bool> > board){
    for(int i = 0; i < p.size(); i++){
        int x = p[i].x;
        int y = p[i].y;
        board[x][y] = false;
    }
    return board;
}

보드판을 채우는 것은 사용한 퍼즐을 인자로 넘겨 간단하게 처리할 수 있다.
왜냐하면 퍼즐에는 좌표정보의 원본이 들어있기 때문이다.

반복문을 통해 보드판의 해당 위치를 1로 만들면 된다.

근데 여기서는 0으로 만들었는데
내가 편하게 풀려고 저 보드판 자체를 반전시켜서 퍼즐판과 동일한 조건으로 만들었다.
(1이 될 때 빈 공간)

이제 전체 코드를 올리고 가장 밑에 main 문을 설명하고 코드 설명을 마치겠다.

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

using namespace std;
struct Point{
    int x;
    int y;
};

vector<vector<bool> > check; // 방문 처리
vector<vector<Point> > puzzleList; // 퍼즐을 담는 리스트
vector<vector<Point> > emptyList; // 빈 공간을 담는 리스트



// 90도 한번 돌리기
vector<vector<bool>> rotateOnce(vector<vector<bool> > origin){

    int c = origin.size(); // 행
    int r = origin.size(); // 열

    // 반환할 90도 돌아간 보드판
    vector<vector<bool>> board;
    vector<bool> row(r);

    for(int i = 0; i < c; i++) board.push_back(row);

    // 90도 돌리는 작업
    for(int i = 0; i < origin.size(); i++){
        for(int j = 0; j < origin[i].size(); j++){
            board[origin.size()-j-1][i] = origin[i][j];
        }
    }
    return board;
}

// 다시 방문하지 않도록 빈 공간 메우기
vector<vector<bool>> fillBoard(vector<Point> p, vector<vector<bool> > board){
    for(int i = 0; i < p.size(); i++){
        int x = p[i].x;
        int y = p[i].y;
        board[x][y] = false;
    }
    return board;
}

// 빈공간, 퍼즐 추출하기 
// select를 통해 보드판, 퍼즐판 구분
vector<Point> getPuzzle(int sx,int sy,vector<vector<bool>> select){
    int dx[] = {0,0,-1,1};
    int dy[] = {-1,1,0,0};
    
    queue<Point> q;
    vector<Point> list;
    check[sx][sy] = true;
    Point p = {sx,sy};
    q.push(p);
    list.push_back(p);


    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= select.size() || ny >= select.size() 
            || check[nx][ny] || !select[nx][ny]) continue;
            check[nx][ny] = true;
            Point np = {nx,ny};
            q.push(np);
            list.push_back(np);
        }
    }
    return list;
}

// (0,0)으로 리포지션 시키는 함수
vector<Point> rePos(vector<Point> p){
    int minX = p[0].x;
    int minY = p[0].y;

    for(int i = 1; i < p.size(); i++){
        minX = min(minX,p[i].x);
        minY = min(minY,p[i].y);
    }

    for(int i = 0; i < p.size(); i++){
        p[i].x -= minX;
        p[i].y -= minY;
    }
    return p;

}
// 두 퍼즐이 일치하는지 비교하는 함수
int comparePuzzle(vector<Point> a, vector<Point> b){
    int answer = 0;
    a = rePos(a);
    b = rePos(b);

    int count = 0;
    // 애초에 개수가 일치하지 않으면 틀림
    if(a.size() != b.size()) return 0;

    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < b.size(); j++){
            if(a[i].x == b[j].x && a[i].y == b[j].y){
                count++;
                break;
            }
        }
    }
    // 일치하는 좌표의 개수가 같을 때만 맞음
    if(count == a.size()) return a.size();
    else return 0;
}

int solution(vector<vector<int> > game_board, vector<vector<int> > table) {
    vector<vector<bool> > board;
    vector<vector<bool> > puzzles;
    for(int i = 0; i < table.size(); i++){
        vector<bool> v1;
        vector<bool> v2;
        vector<bool> v3;
        for(int j = 0; j < table[i].size(); j++){
            v1.push_back(!game_board[i][j]);
            v2.push_back(table[i][j]);
            v3.push_back(false);
        }
        board.push_back(v1);
        puzzles.push_back(v2);
        check.push_back(v3);
    }

    for(int i = 0; i < puzzles.size(); i++)
        for(int j = 0; j < puzzles[i].size(); j++)
            if(!check[i][j] && puzzles[i][j]) puzzleList.push_back(getPuzzle(i,j,puzzles));

    int count = 4;
    int answer = 0;
    fill(check.begin(),check.end(),vector<bool>(check.size(),false));
    
    while(count--){
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board.size(); j++)
                if(board[i][j] && !check[i][j]) 
                    emptyList.push_back(getPuzzle(i,j,board));

        for(int i = 0; i < puzzleList.size(); i++){
            for(int j = 0; j < emptyList.size(); j++){
                int val = comparePuzzle(puzzleList[i],emptyList[j]);
                if(val != 0) {
                    answer += val;
                    board = fillBoard(emptyList[j],board);
                    puzzleList.erase(puzzleList.begin()+i);
                    emptyList.erase(emptyList.begin()+j);
                    i--;
                    break;
                }
            }
        }
        board = rotateOnce(board);

        fill(check.begin(),check.end(),vector<bool>(check.size(),false));
    }
    return answer;
}

main에서는 입력을 받는 것과 퍼즐 추출, 빈 공간 추출을 실행시켜 주었다.

핵심적으로 보아야 하는 부분은 while문 안에 부분인데,
회전은 4번 이상은 의미 없기 때문에 4번 이상은 돌리지 않기로 했다.

매 회전마다 빈 공간을 추출하고,
그 값을 comparePuzzle을 통해 비교하여 일치하면 블록의 개수를 반환한다.

그리고 fillBoard를 통해 일치했던 블록의 좌표를 가져와 그 공간을 메워주고
puzzleList와 emptyList에서 지워준다.

그리고 해당 반복문을 탈출하여 해당 비교를 끝낸다.

모든 puzzleList에 있는 퍼즐의 탐색이 끝났다면,
보드판을 90도 돌리고 다시 한번 위 과정을 반복한다.

그래서 최종적으로 나오는 answer가 답이 된다.

 

---

시행착오

역대급으로 오래 걸린 문제이다.

자괴감도 많이 오고 중간중간에 인터넷을 참고해도
뭔가 성이 차지 않아서 나만의 풀이법으로 풀어보려고 노력했다.

구현이 약하다는 문제가 여기서 여실히 드러났다.
근데 이건 솔직히 구현문제다. 멘탈 다 망가져갔다.