[프로그래머스][C++] 위클리 챌린지 3주차 퍼즐 조각 채우기

WestCoast·2021년 8월 18일
BFS구현알고리즘위클리 챌린지프로그래머스회전행렬
0

코딩테스트 풀이

목록 보기
5/13
post-thumbnail

문제

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

풀이

알고리즘

간단하게

  1. game_board의 원소들을 반전 0->1, 1->0
GameBoardReversing(game_board);
  1. game_board의 (퍼즐 하나를 넣을 수 있는)빈 칸 덩어리들을 찾고 분류 후 각 빈 칸 덩어리 좌표를 [0,0] 기준으로 변경
vector<vector<pair<int, int>>> boardBlanks = PuzzleDivision(game_board);
  1. table의 퍼즐들을 찾고 분류 후 각 퍼즐 좌표를 [0,0] 기준으로 변경
vector<vector<pair<int, int>>> puzzles = PuzzleDivision(table);
  1. boardBlanks에 puzzles를 회전시켜보면서 매칭
int answer = PuzzleMatching(boardBlanks, puzzles);
  1. 사용할 함수들
//게임보드 0-1 반전
void GameBoardReversing(vector<vector<int>> &my_board);
//보드의 빈칸 덩어리들과 퍼즐들의 좌표를 [0,0] 기준으로 변경
vector<vector<pair<int, int>>> PuzzleReduction(vector<vector<pair<int, int>>> puzzles);
//퍼즐 나누기
vector<vector<pair<int, int>>> PuzzleDivision(vector<vector<int>> &tables);
//행렬 회전: -90도 회전(반시계방향)
vector<vector<pair<int, int>>> PuzzleRotation(vector<vector<pair<int, int>>> puzzles);
//퍼즐 맞추기
int PuzzleMatching(vector<vector<pair<int, int>>> boardBlanks, vector<vector<pair<int, int>>> puzzles);
  1. 메인 실행 함수
int solution(vector<vector<int>> game_board, vector<vector<int>> table)
{
    // 1) game_board의 원소들을 반전
    GameBoardReversing(game_board);

    // 2) game_board의 빈칸 덩어리들 탐색
    vector<vector<pair<int, int>>> boardBlanks = PuzzleDivision(game_board);

    // 3) table의 조각들 탐색
    vector<vector<pair<int, int>>> puzzles = PuzzleDivision(table);

    // 4) 3번에서 찾은 조각들을 2번에서 찾은 빈칸들과 비교하며 퍼즐 맞추기
    int answer = PuzzleMatching(boardBlanks, puzzles);

    return answer;
}

자세하게

    1. game_board의 원소들을 반전시켜 준 이유는 game_board의 빈 칸과 table의 조각을 탐색할 때 PuzzleDivision 함수를 통해서 원소 값이 1일 때 처리를 해주도록 하기 위함임. 간단히 말하면 함수 하나로 둘 다 조사하고 싶어서.

  • 2~3. PuzzleDivision 함수가 매개변수로 주어진 행렬에서 BFS를 이용하여 해당 문제 조건에 맞는 조각을 찾고 분류 후, PuzzleDivision 내부에서 PuzzleReduction 함수를 이용해서 각 조각 좌표를 [0,0] 기준으로 변경함.
    PuzzleDivision: 매개변수로 주어진 행렬을 해당 문제 규칙에 따라 BFS 탐색
    PuzzleReduction: 퍼즐3을 예시로 설명하면 min_i=1, min_j=1이고 퍼즐3 모든 원소들에 대해 [i-min_i, j-min_j]를 함. 별거 없다.
<탐색만 완료한 퍼즐>
퍼즐 1 [0,0] [1,0]
퍼즐 2 [0,3] [0,4] [1,4] [2,4] [2,5]
퍼즐 3 [1,2] [2,1] [2,2] [3,2]
퍼즐 4 [4,0] [4,1] [5,1]
퍼즐 5 [4,3] [4,4]
<[0,0] 기준으로 정렬까지 완료한 퍼즐>
퍼즐 1 [0,0] [1,0]
퍼즐 2 [0,0] [0,1] [1,1] [2,1] [2,2] 
퍼즐 3 [0,1] [1,0] [1,1] [2,1]
퍼즐 4 [0,0] [0,1] [1,1]
퍼즐 5 [0,0] [0,1]
    1. 마지막 PuzzleMatching 함수에서는 위에서 겨우겨우 분류해낸 boardBlanks와 puzzles를 매개변수로 하여 맞춰본다.
      마음 단단히 먹길 바란다. 이 함수는 4중 for문 구조로 이루어져 있다.
int answer = 0;  //채워진 칸 수를 저장하며, 마지막에 return 해줄 것
  • 1중 for문 : for (int r = 0; r < 4; r++)
    먼저 회전 하지 않은 puzzles를 비교한 후 3번(총 -270도) 회전해가면서 puzzles를 비교할 것이므로 총 4번 반복
    • 2중 for문 : for (int i = 0; i < boardBlanks.size(); i++)
      boardBlanks.size()만큼 반복하면서 게임보드에 빈 칸 덩어리를 모두 돈다.
      • 3중 for문 : for (int j = 0; j < puzzles.size(); j++)
        게임보드의 빈 칸 덩어리 하나(boardBlanks[i])를 잡고 puzzles.size()만큼 반복하면서 boardBlanks[i].size()와 puzzles[j].size()가 같은 것이 있는지 비교한다.
        • 4중 for문 : for (k = 0; k < boardBlanks[i].size(); k++)
          3중 for문에서 같은 것을 찾았다면, boardBlanks[i][k]와 puzzles[j][k]가 모두 동일한 값인지 비교한다.
          만약 모두 같은 값이었다면 퍼즐을 넣을 수 있다는 뜻이므로 해당 boardBlanks[i]와 puzzles[j]를 삭제.
          k만큼 게임 보드가 채워졌으므로 answer += k 해준 후 break.
  • 1중 for문
    PuzzleRotation 함수를 이용해서 puzzles를 -90도 회전한 후 반복.

코드

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

void GameBoardReversing(vector<vector<int>> &my_board);
vector<vector<pair<int, int>>> PuzzleReduction(vector<vector<pair<int, int>>> puzzles);
vector<vector<pair<int, int>>> PuzzleDivision(vector<vector<int>> &tables);
vector<vector<pair<int, int>>> PuzzleRotation(vector<vector<pair<int, int>>> puzzles);
int PuzzleMatching(vector<vector<pair<int, int>>> boardBlanks, vector<vector<pair<int, int>>> puzzles);

//메인 실행 함수
int solution(vector<vector<int>> game_board, vector<vector<int>> table)
{
    // 1) game_board의 원소들을 반전
    GameBoardReversing(game_board);

    // 2) game_board의 빈칸 덩어리들 탐색
    vector<vector<pair<int, int>>> boardBlanks = PuzzleDivision(game_board);

    // 3) table의 조각들 탐색
    vector<vector<pair<int, int>>> puzzles = PuzzleDivision(table);

    // 4) 3번에서 찾은 조각들을 2번에서 찾은 빈칸들과 비교하며 퍼즐 맞추기
    int answer = PuzzleMatching(boardBlanks, puzzles);

    return answer;
}

//게임보드 0-1 반전
void GameBoardReversing(vector<vector<int>> &my_board)
{
    for (int i = 0; i < my_board.size(); i++)
    {
        for (int j = 0; j < my_board[i].size(); j++)
        {
            if (my_board[i][j])
                my_board[i][j] = 0;
            else
                my_board[i][j] = 1;
        }
    }
}

//보드의 빈칸 덩어리들과 퍼즐들의 좌표를 [0,0] 기준으로 변경
vector<vector<pair<int, int>>> PuzzleReduction(vector<vector<pair<int, int>>> puzzles)
{
    for (int i = 0; i < puzzles.size(); i++)
    {
        int minI = 1000;
        int minJ = 1000;

        for (int j = 0; j < puzzles[i].size(); j++)
        {
            if (puzzles[i][j].first < minI)
                minI = puzzles[i][j].first;

            if (puzzles[i][j].second < minJ)
                minJ = puzzles[i][j].second;
        }

        for (int j = 0; j < puzzles[i].size(); j++)
        {
            puzzles[i][j].first -= minI;
            puzzles[i][j].second -= minJ;
        }
    }

    return puzzles;
}

//퍼즐 나누기
vector<vector<pair<int, int>>> PuzzleDivision(vector<vector<int>> &tables)
{
    vector<vector<pair<int, int>>> result;
    int new_i = 0;

    while (true)
    {
        vector<pair<int, int>> temp;
        queue<pair<int, int>> q;

        for (int i = new_i; i < tables.size(); i++)
        {
            for (int j = 0; j < tables.size(); j++)
            {
                if (tables[i][j] == 1)
                {
                    q.push(make_pair(i, j));
                    tables[i][j] = 0;
                    new_i = i;
                    break;
                }
            }

            if (!q.empty())
                break;
        }

        if (q.empty())
            break;

        while (!q.empty())
        {
            int cur_i = q.front().first;
            int cur_j = q.front().second;
            temp.push_back(q.front());
            q.pop();

            if (cur_i > 0 && tables[cur_i - 1][cur_j]) //상
            {
                q.push(make_pair(cur_i - 1, cur_j));
                tables[cur_i - 1][cur_j] = 0;
            }
            if (cur_i < tables.size() - 1 && tables[cur_i + 1][cur_j]) //하
            {
                q.push(make_pair(cur_i + 1, cur_j));
                tables[cur_i + 1][cur_j] = 0;
            }
            if (cur_j > 0 && tables[cur_i][cur_j - 1]) //좌
            {
                q.push(make_pair(cur_i, cur_j - 1));
                tables[cur_i][cur_j - 1] = 0;
            }
            if (cur_j < tables.size() - 1 && tables[cur_i][cur_j + 1]) //우
            {
                q.push(make_pair(cur_i, cur_j + 1));
                tables[cur_i][cur_j + 1] = 0;
            }
        }

        sort(temp.begin(), temp.end());

        result.push_back(temp);
    }

    result = PuzzleReduction(result);
    return result;
}

//행렬 회전: -90도 회전(반시계방향)
vector<vector<pair<int, int>>> PuzzleRotation(vector<vector<pair<int, int>>> puzzles)
{
    for (int i = 0; i < puzzles.size(); i++)
    {
        int N = -1;
        //N = max(puzzles[i][j].first || puzzles[i][j].second)
        for (int j = 0; j < puzzles[i].size(); j++)
        {
            if (puzzles[i][j].first > N)
                N = puzzles[i][j].first;

            if (puzzles[i][j].second > N)
                N = puzzles[i][j].second;
        }

        for (int j = 0; j < puzzles[i].size(); j++)
            puzzles[i][j] = make_pair(N - puzzles[i][j].second, puzzles[i][j].first);

        sort(puzzles[i].begin(), puzzles[i].end());
    }

    puzzles = PuzzleReduction(puzzles);
    return puzzles;
}

//퍼즐 맞추기
int PuzzleMatching(vector<vector<pair<int, int>>> boardBlanks, vector<vector<pair<int, int>>> puzzles)
{
    int temp_cnt = 1;
    int answer = 0;

    for (int r = 0; r < 4; r++)
    {
        for (int i = 0; i < boardBlanks.size(); i++)
        {
            for (int j = 0; j < puzzles.size(); j++)
            {
                if (boardBlanks[i].size() == puzzles[j].size())
                {
                    int k = 0;
                    for (k = 0; k < boardBlanks[i].size(); k++)
                        if (boardBlanks[i][k] != puzzles[j][k])
                            break;

                    if (k == boardBlanks[i].size())
                    {
                        boardBlanks.erase(boardBlanks.begin() + i);
                        puzzles.erase(puzzles.begin() + j);
                        i--;

                        answer += k;
                        break;
                    }
                }
            } //end_for_j
        }     //end_for_i

        puzzles = PuzzleRotation(puzzles);
    } //end_for_r

    return answer;
}

주석코드

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

void GameBoardReversing(vector<vector<int>> &my_board);
vector<vector<pair<int, int>>> PuzzleReduction(vector<vector<pair<int, int>>> puzzles);
vector<vector<pair<int, int>>> PuzzleDivision(vector<vector<int>> &tables);
vector<vector<pair<int, int>>> PuzzleRotation(vector<vector<pair<int, int>>> puzzles);
int PuzzleMatching(vector<vector<pair<int, int>>> boardBlanks, vector<vector<pair<int, int>>> puzzles);

// 테스트 케이스
vector<vector<int>> game_board = {{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}};
vector<vector<int>> table = {{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}};

vector<vector<int>> game_board2 = {{0, 0, 0}, {1, 1, 0}, {1, 1, 1}};
vector<vector<int>> table2 = {{1, 1, 1}, {1, 0, 0}, {0, 0, 0}};

vector<vector<int>> game_board3 = {{0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0}, {1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1}, {0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1}, {0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0}, {1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0}, {0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1}, {0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}};
vector<vector<int>> table3 = {{1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1}, {1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0}, {0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0}, {1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1}, {1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1}, {1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1}};

//-------------------------------------------------------------------------------------------------------------

//메인 실행 함수
int solution(vector<vector<int>> game_board, vector<vector<int>> table)
{
    // 1) game_board의 원소들을 반전
    GameBoardReversing(game_board);

    // 2) game_board의 빈칸 덩어리들 탐색
    vector<vector<pair<int, int>>> boardBlanks = PuzzleDivision(game_board);

    cout << "<boardBlanks>\n";
    for (int i = 0; i < boardBlanks.size(); i++)
    {
        cout << "빈 칸 덩어리 " << i + 1 << endl;
        for (int j = 0; j < boardBlanks[i].size(); j++)
            cout << "[" << boardBlanks[i][j].first << "," << boardBlanks[i][j].second << "] ";
        cout << "\n\n";
    }
    cout << "----------------\n\n";

    // 3) table의 조각들 탐색
    vector<vector<pair<int, int>>> puzzles = PuzzleDivision(table);

    cout << "<puzzles>\n";
    for (int i = 0; i < puzzles.size(); i++)
    {
        cout << "퍼즐 " << i + 1 << endl;
        for (int j = 0; j < puzzles[i].size(); j++)
            cout << "[" << puzzles[i][j].first << "," << puzzles[i][j].second << "] ";
        cout << "\n\n";
    }
    cout << "----------------\n\n";

    // 4) 3번에서 찾은 조각들을 2번에서 찾은 빈칸들과 비교하며 퍼즐 맞추기
    int answer = PuzzleMatching(boardBlanks, puzzles);

    cout << "answer: " << answer << endl;
    return answer;
}

//게임보드 0-1 반전
void GameBoardReversing(vector<vector<int>> &my_board)
{
    for (int i = 0; i < my_board.size(); i++)
    {
        for (int j = 0; j < my_board[i].size(); j++)
        {
            if (my_board[i][j])
                my_board[i][j] = 0;
            else
                my_board[i][j] = 1;
        }
    }
}

//보드의 빈칸 덩어리들과 퍼즐들의 좌표를 [0,0] 기준으로 변경
//PuzzleDivision 함수와 PuzzleRotation 함수에서 사용
vector<vector<pair<int, int>>> PuzzleReduction(vector<vector<pair<int, int>>> puzzles)
{
    //퍼즐 갯수만큼 반복
    for (int i = 0; i < puzzles.size(); i++)
    {
        int minI = 1000;
        int minJ = 1000;

        //각 퍼즐 길이만큼 반복
        for (int j = 0; j < puzzles[i].size(); j++)
        {
            //minI = min(puzzles[i][0]의 행 값 ~ puzzles[i][마지막 값]의 행 값)
            if (puzzles[i][j].first < minI)
                minI = puzzles[i][j].first;

            //minJ = min(puzzles[i][0]의 열 값 ~ puzzles[i][마지막 값]의 열 값)
            if (puzzles[i][j].second < minJ)
                minJ = puzzles[i][j].second;
        }

        //각 퍼즐 길이만큼 반복
        for (int j = 0; j < puzzles[i].size(); j++)
        {
            //puzzles[i][j]]의 행 값 -= minI
            puzzles[i][j].first -= minI;
            //puzzles[i][j]]의 열 값 -= minJ
            puzzles[i][j].second -= minJ;
        }
    }

    return puzzles;
}

//퍼즐 나누기
//BFS를 이용해서 탐색
vector<vector<pair<int, int>>> PuzzleDivision(vector<vector<int>> &tables)
{
    //return 해줄 퍼즐을 저장할 것
    vector<vector<pair<int, int>>> result;
    //중복 탐색을 줄여서 탐색 효율 증가
    int new_i = 0;

    while (true)
    {
        vector<pair<int, int>> temp; //퍼즐 한 개를 저장하기 위한 temp
        queue<pair<int, int>> q;     //BFS 탐색을 위한 큐

        //퍼즐의 첫번째 원소를 찾으면 큐에 push
        for (int i = new_i; i < tables.size(); i++)
        {
            for (int j = 0; j < tables.size(); j++)
            {
                if (tables[i][j] == 1)
                {
                    q.push(make_pair(i, j));
                    tables[i][j] = 0; //인풋으로 주어진 table을 visited 대용으로 사용
                    new_i = i;        //마지막으로 탐색한 i를 저장하여 다음부터는 new_i부터 탐색
                    break;
                }
            }

            //퍼즐의 첫번째 원소를 찾았다면 break
            if (!q.empty())
                break;
        }

        //퍼즐이 더이상 없다면 탐색 종료
        if (q.empty())
            break;

        while (!q.empty())
        {
            int cur_i = q.front().first;
            int cur_j = q.front().second;
            temp.push_back(q.front()); //퍼즐의 원소들을 저장
            q.pop();

            //퍼즐 원소의 상,하,좌,우를 탐색해보고 존재한다면
            //큐에 push하고 방문한 위치 표시
            if (cur_i > 0 && tables[cur_i - 1][cur_j]) //상
            {
                q.push(make_pair(cur_i - 1, cur_j));
                tables[cur_i - 1][cur_j] = 0;
            }
            if (cur_i < tables.size() - 1 && tables[cur_i + 1][cur_j]) //하
            {
                q.push(make_pair(cur_i + 1, cur_j));
                tables[cur_i + 1][cur_j] = 0;
            }
            if (cur_j > 0 && tables[cur_i][cur_j - 1]) //좌
            {
                q.push(make_pair(cur_i, cur_j - 1));
                tables[cur_i][cur_j - 1] = 0;
            }
            if (cur_j < tables.size() - 1 && tables[cur_i][cur_j + 1]) //우
            {
                q.push(make_pair(cur_i, cur_j + 1));
                tables[cur_i][cur_j + 1] = 0;
            }
        }

        sort(temp.begin(), temp.end());

        //퍼즐 한 개의 탐색을 마치면 result에 저장
        result.push_back(temp);
    }

    //모든 퍼즐들의 좌표 변경
    result = PuzzleReduction(result);
    return result;
}

//행렬 회전: -90도 회전(반시계방향)
//퍼즐 하나를 가상으로 정사각 행렬로 치환하여 회전
//PuzzleMatching 함수에서 사용
vector<vector<pair<int, int>>> PuzzleRotation(vector<vector<pair<int, int>>> puzzles)
{
    for (int i = 0; i < puzzles.size(); i++)
    {
        int N = -1;
        //N = max(puzzles[i][j].first || puzzles[i][j].second)
        for (int j = 0; j < puzzles[i].size(); j++)
        {
            if (puzzles[i][j].first > N)
                N = puzzles[i][j].first;

            if (puzzles[i][j].second > N)
                N = puzzles[i][j].second;
        }

        for (int j = 0; j < puzzles[i].size(); j++)
            //-90도 회전한 퍼즐[i, j] = 기존 퍼즐[N - puzzles[i][j]의 j, puzzles[i][j]의 i]
            puzzles[i][j] = make_pair(N - puzzles[i][j].second, puzzles[i][j].first);

        sort(puzzles[i].begin(), puzzles[i].end());
    }

    //모든 퍼즐들의 좌표 변경
    puzzles = PuzzleReduction(puzzles);
    return puzzles;
}

//퍼즐 맞추기
int PuzzleMatching(vector<vector<pair<int, int>>> boardBlanks, vector<vector<pair<int, int>>> puzzles)
{
    cout << "<PuzzleMatching>\n";
    int temp_cnt = 1;
    int answer = 0; //answer = 채워진 칸 수

    //회전 4번만큼 반복
    for (int r = 0; r < 4; r++)
    {
        //board의 빈 칸 덩어리 갯수만큼 반복
        for (int i = 0; i < boardBlanks.size(); i++)
        {
            //퍼즐 갯수만큼 반복
            for (int j = 0; j < puzzles.size(); j++)
            {
                //빈 칸 덩어리 크기와 퍼즐 크기가 같다면 같은지 조사
                if (boardBlanks[i].size() == puzzles[j].size())
                {
                    int k = 0;
                    //빈 칸 덩어리 크기만큼 반복
                    for (k = 0; k < boardBlanks[i].size(); k++)
                        //빈 칸 좌표와 퍼즐 좌표가 하나라도 다르다면 break
                        if (boardBlanks[i][k] != puzzles[j][k])
                            break;

                    //모든 좌표가 동일하다면
                    if (k == boardBlanks[i].size())
                    {
                        cout << "회전: " << r * -90 << "도" << endl;
                        cout << "매칭: boardBlanks " << i + temp_cnt++ << " & puzzle" << endl;
                        cout << "[i,j]: ";
                        for (int x = 0; x < puzzles[j].size(); x++)
                            cout << "[" << puzzles[j][x].first << "," << puzzles[j][x].second << "] ";
                        cout << "\n\n";

                        //해당 빈 칸 덩어리와 퍼즐이 매칭되었으므로 삭제
                        boardBlanks.erase(boardBlanks.begin() + i);
                        puzzles.erase(puzzles.begin() + j);
                        i--;

                        answer += k; //answer += 채워진 칸 수
                        break;
                    }
                }
            } //end_for_j
        }     //end_for_i

        //퍼즐을 회전시키면서 매칭
        puzzles = PuzzleRotation(puzzles);
    } //end_for_r

    return answer;
}

int main()
{
    solution(game_board, table);
}

테스트 케이스 출력

<boardBlanks>
빈 칸 덩어리 1
[0,0] [0,1] [1,1] [2,1] [2,2]

빈 칸 덩어리 2
[0,0] [1,0]

빈 칸 덩어리 3
[0,0] [0,1] [1,0]

빈 칸 덩어리 4
[0,1] [1,0] [1,1] [1,2]

빈 칸 덩어리 5
[0,1] [1,0] [1,1]

빈 칸 덩어리 6
[0,0]

--------------------------------

<puzzles>
퍼즐 1
[0,0] [1,0]

퍼즐 2
[0,0] [0,1] [1,1] [2,1] [2,2]

퍼즐 3
[0,1] [1,0] [1,1] [2,1]

퍼즐 4
[0,0] [0,1] [1,1]

퍼즐 5
[0,0] [0,1]

--------------------------------

<PuzzleMatching>
회전: 0도
매칭: boardBlanks 1 & puzzle
[i,j]: [0,0] [0,1] [1,1] [2,1] [2,2] 

회전: 0도
매칭: boardBlanks 2 & puzzle
[i,j]: [0,0] [1,0]

회전: -90도
매칭: boardBlanks 3 & puzzle
[i,j]: [0,0] [0,1] [1,0]

회전: -270도
매칭: boardBlanks 4 & puzzle
[i,j]: [0,1] [1,0] [1,1] [1,2]

--------------------------------

answer: 14

여담

풀어본 문제들 중에 가장 오래 잡고 있던 문제를 갱신했다.
사실 위클리 챌린지 1,2주차는 프로그래머스 레벨 1~2정도밖에 안되는 수준이라 이번 주차도 끽해야 어려우면 얼마나 어려울까 싶었는데 이 문제, 어렵다. 어렵다기보다는 열받는다는 표현이 더 맞는거 같기도 하다.
문제에서 요구하는 기능이 일단 너무 많다. 퍼즐 쪼개고 빙글빙글 돌리고 맞추고 어쩌고 저쩌고 하라는게 너무 많아서 열받는다.
그래도 불행중 다행은 해당 문제의 틀린 예시에서 보여주는 것처럼 퍼즐을 맞추는 것도 인정된다고 한다면... 생각도 하기 싫다.
3주차가 이 레벨이면 다음주부터는 무슨 문제를 낼 것인가 하는 두려움이 앞선다.

처음에 퍼즐을 쪼갤 때 DFS를 사용해서 하려고 했는데 잘 되지 않아서 코드 앞에서 명상타임을 꽤 길게 가졌는데 생각해보니 BFS로 금방 해결할 수 있었다. 그렇다. 필자는 좀 멍청한 듯 하다. 그래도 결과가 좋으니 다 좋은 것 아닐까? 아닌가?
사실 문제를 풀다가 이 문제를 풀 수 있을까 싶었는데 풀기 시작한걸 못푼다는 것도 자존심이 용납을 못하는 성격이라 그런지 결국에는 승리했다.

확실히 문제가 난이도가 있어서 그런지 포스팅 하는 현재 3주차 완료는 140명밖에 되지 않는다. 2주차가 2647명인걸 보면 차이가 확연하다.

마지막으로 포스팅 하면서 코드를 다시 보니 좀 개선할만한 여지가 있는 부분이 있는 것 같기도 한데, 포스팅이 길어져서 이곳에는 남기지 않는다...

profile
WestCoast
게임... 만들지 않겠는가..
이전 포스트

[백준][C++][백트래킹] 9663번 N-Queen

다음 포스트

[프로그래머스][C++] 위클리 챌린지 4주차 직업군 추천하기

0개의 댓글