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

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

using namespace std;

//type = 보드는 0, 테이블은 1을 확인
void Check(int type, vector<vector<int>>& type_board,
    vector<vector<pair<int, int>>>& puzzle);

//90도만큼씩 돌려보면서 같은 도형의 개수를 찾는다.
int Degree(vector<vector<pair<int, int>>> boards,
    vector<vector<pair<int, int>>> tables);

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = -1;

    vector<vector<pair<int, int>>> boards;
    vector<vector<pair<int, int>>> tables;

    Check(0, game_board, boards);
    Check(1, table, tables);

    answer = Degree(boards, tables);

    return answer;
}

void Check(int type, vector<vector<int>>& type_board,
    vector<vector<pair<int, int>>>& puzzle)
{
    int lange = type_board.size();

    for (int i = 0; i < type_board.size(); i++)
    {
        for (int j = 0; j < type_board.size(); j++)
        {
            if (type_board[i][j] == type)
            {
                //지나간보드 채우기
                queue<pair<int, int>> dfs;
                vector<pair<int, int>>temp;
                dfs.push({ i, j });
                type_board[i][j] = !type;

                while (!dfs.empty())
                {
                    int first = dfs.front().first;
                    int second = dfs.front().second;
                    dfs.pop();

                    //첫위치를 빼주어 0, 0를 스타트로 맞춰준다.
                    temp.push_back({ first - i, second - j });

                    //상하좌우에 퍼즐이 있나 확인
                    if (second + 1 < lange && type_board[first][second + 1] == type)
                    {
                        dfs.push({ first, second + 1 });
                        type_board[first][second + 1] = !type;
                    }
                    if (first + 1 < lange && type_board[first + 1][second] == type)
                    {
                        dfs.push({ first + 1, second });
                        type_board[first + 1][second] = !type;
                    }
                    if (first - 1 >= 0 && type_board[first - 1][second] == type)
                    {
                        dfs.push({ first - 1, second });
                        type_board[first - 1][second] = !type;
                    }
                    if (second - 1 >= 0 && type_board[first][second - 1] == type)
                    {
                        dfs.push({ first, second - 1 });
                        type_board[first][second - 1] = !type;
                    }
                }//while(dfs.empty())

                //한 퍼즐 완료
                puzzle.push_back(temp);
            }

        }//for(int j = 0; j < type_board.size(); j++)
    }
}

int Degree(vector<vector<pair<int, int>>> boards,
    vector<vector<pair<int, int>>> tables)
{
    int result = 0;
    //boards에 tables의 것이 같은 도형인지 확인
    for (int i = 0; i < boards.size(); i++)
    {
        for (int j = 0; j < tables.size(); j++)
        {
            //칸 수가 같은 도형일 때
            if (boards[i].size() == tables[j].size())
            {
                int test4 = 0;
                bool cleared = false;

                while(test4 != 4)   //4각도 확인
                {
                    int counts = 0;
                    test4++;

                    sort(boards[i].begin(), boards[i].end());

                    for (int k = 0; k < tables[j].size(); k++)  //맞는지 확인
                    {
                        if (boards[i][k].first == tables[j][k].first &&
                            boards[i][k].second == tables[j][k].second)
                            counts++;
                    }

                    if (counts == tables[j].size()) //맞다면 칸의 개수만큼 추가 후 종료
                    {
                        result += counts;
                        cleared = true;
                        tables.erase(tables.begin() + j);
                        break;
                    }
                    else
                    {
                        for (int k = 0; k < tables[j].size(); k++)  //90도 회전
                        {
                            int tempTable = tables[j][k].first;
                            tables[j][k].first = -tables[j][k].second;
                            tables[j][k].second = tempTable;
                        }

                        sort(tables[j].begin(), tables[j].end());

                        int tempfirst = tables[j][0].first;
                        int tempsecond = tables[j][0].second;

                        for (int k = 0; k < tables[j].size(); k++)  //회전 후 0,0으로 정렬
                        {
                            tables[j][k].first -= tempfirst;
                            tables[j][k].second -= tempsecond;
                        }
                    }
                }//while(test4 != 4)

                if (cleared == true) break;

            }//if (boards[i].size() == tables[j].size())
        }//for (int j = 0; j < tables.size(); j++)
    }//for (int i = 0; i < boards.size(); i++)

    return result;
}

풀이

확인 -> 저장 -> 비교

 

확인

- 보드는 0, 테이블은 1로 채워야할 칸과 퍼즐이 주어진다.

- 보드와 테이블이 서로 반대이므로 확인할 때 type값을 주어 한 함수에서 해결

- 보드와 테이블을 확인했으면 다시 확인하지 않도록 type값의 반대의 값을 주어 채워놓으면 된다. ( !type )

 

저장

- 확인과 동시에 저장한다.

- 저장할 때에는 기준점을 만들기위해 0, 0으로 기준을 맞추어준다.

- 처음 발견한 곳을 0, 0으로 한다.

- 처음 발견한 곳의 값만큼 빼준다. 
temp.push_back({ first - i, second - j });

 

비교

- 저장한 부분들을 하나씩 비교한다.

- .size()해주어 각 칸수를 먼저 비교해준다.

- 이 때 90도로 회전하며 비교하는데 좌표의 회전 공식을 사용하였다.

x, y가 있으면 -y, x로 바꾸면 회전한다.

 

- 회전 뒤에는 sort해서 정렬해준 뒤 다시 0,0으로 좌표를 맞추어준다.

- 다시 비교해준다.

- 비교한 것이 맞다면 칸 수만큼 답안에 추가해준다.

 

 

 

도움 자료 : http://godingmath.com/rotation90

소소하지만 확실한 테크닉 - 90도 회전이동 | godingMath

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차_퍼즐 조각 채우기

 

 

총 4시간정도 걸린듯하다. 하나씩 풀어나간다면 쉬울 것이고 한번에 해결하려한다면 어려웠었다.

처음에 어떻게 풀지 생각만 거의 30분은 했다.

각 과정을 따로 메모장에 정리하며 어떻게 풀지를 구상하는 것이 도움이 되었다.

 

2시간10분 : 0,0기준으로 조각들을 넣는 기능까지 해결.

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

using namespace std;



//type = 보드는 0, 테이블은 1을 확인
void check(int type, vector<vector<int>>& type_board,
    vector<vector<pair<int, int>>>& puzzle);

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = -1;

    vector<vector<pair<int, int>>> boards;
    vector<vector<pair<int, int>>> tables;

    check(0, game_board, boards);
    check(1, table, tables);


    return answer;
}

void check(int type, vector<vector<int>>& type_board,
    vector<vector<pair<int, int>>>& puzzle)
{
    int lange = type_board.size();

    for (int i = 0; i < type_board.size(); i++)
    {
        for (int j = 0; j < type_board.size(); j++)
        {
            if (type_board[i][j] == type)
            {
                //지나간보드 채우기
                queue<pair<int, int>> dfs;
                vector<pair<int, int>>temp;
                dfs.push({ i, j });
                type_board[i][j] = !type;

                while (!dfs.empty())
                {
                    int first = dfs.front().first;
                    int second = dfs.front().second;
                    dfs.pop();

                    //첫위치를 빼주어 0, 0를 스타트로 맞춰준다.
                    temp.push_back({ first - i, second - j });

                    //상하좌우에 퍼즐이 있나 확인
                    if (second + 1 < lange && type_board[first][second + 1] == type)
                    {
                        dfs.push({ first, second + 1 });
                        type_board[first][second + 1] = !type;
                    }
                    if (first + 1 < lange && type_board[first + 1][second] == type)
                    {
                        dfs.push({ first + 1, second });
                        type_board[first + 1][second] = !type;
                    }
                    if (first - 1 >= 0 && type_board[first - 1][second] == type)
                    {
                        dfs.push({ first - 1, second });
                        type_board[first - 1][second] = !type;
                    }
                    if (second - 1 >= 0 && type_board[first][second - 1] == type)
                    {
                        dfs.push({ first, second - 1 });
                        type_board[first][second - 1] = !type;
                    }
                }//while(dfs.empty())

                //한 퍼즐 완료
                puzzle.push_back(temp);
            }

        }//for(int j = 0; j < type_board.size(); j++)
    }
}