[백준] 2641 다각형그리기, C++

2641번: 다각형그리기

문제 요약

처음 주어지는 모양수열로 만들어진 도형과 같은 도형이 나오는 수열을 찾는 문제이다.
모양수열은 방향을 가리키는 숫자 (1: 우, 2: 상, 3: 좌, 4: 하)로 이루어진 수열이다.
회전이나 뒤집었을때 같은 도형은 다른 것으로 생각한다.

 

접근

1. 쉬운 도형을 직접 그려서 규칙 확인

크기가 1인 정사각형의 모양수열을 확인했다.
좌측 상위의 점을 시작점으로 잡았을 때 시계방향으로 도는 모양수열은 1-4-3-2가 된다.
같은 시작점이고 반시계방향인 모양수열은 4-1-2-3이 된다.
위의 방식으로 모든 점에 대해서 시작점을 잡고 시계방향, 반시계 방향인 모양수열을 모두 구하면 다음과 같다.
1-2-3-4, 2-3-4-1, 3-4-1-2, 4-1-2-3, 4-3-2-1, 3-2-1-4 ,2-1-4-3, 1-4-3-2

위의 모양수열을 보면 규칙을 찾을수 있다.
시계방향으로 구한 모양수열과 반시계방향으로 구한 모양수열에 대해서 시작점을 다르게 해서 순환시키면 다른 모양수열을 만들수 있다.
즉, 1-4-3-2에서 두번째를 시작점으로 두고 순환하면 4-3-2-1이 된다.

여기서 이 문제의 해결법을 도출해낼수 있었다.

 

알고리즘

1. 처음 주어지는 모양수열을 저장하고, 이 모양수열을 바탕으로 반대방향으로 도는 모양수열을 만든다.
   • 같은 도형인지 확인할 때 쉽게 하기위해 정방향과 역방향 모양수열의 길이를 두배로 만든다.
   • 처음 받은 모양수열이 1 4 3 2 이라고 하면 만들어지는 모양수열은 1 4 3 2 1 4 3 2와 3 2 1 4 3 2 1 4가 된다.
2. 그 이후에 받는 입력에 대해서 같은 도형인지 확인한다.
   • 1에서 만들어진 것에 대해 입력이 부분 수열인지만 확인하면 된다.
   • 들어온 입력이 2 1 4 3이라고 해보자. 1 4 3 2 1 4 3 2와 3 2 1 4 3 2 1 4에서 부분 수열이 2 1 4 3이 있는지 확인하면 된다. 이 경우는 1 4 3 2-1-4-3 2 여기에 있으므로 같은 도형이 된다.
   • 들어온 입력이 1 3 2 4 라고 해보자. 1 4 3 2 1 4 3 2와 3 2 1 4 3 2 1 4에서 부분 수열을 찾을수 없으므로 같은 도형이 아니다.(물론 이 입력은 도형이 만들어지지 않는다)
   • 확인하는 알고리즘은 모든 길이를 확인하는 방식으로 만들었다.

 

새로 알게된 것

1. vector 라이브러리
   • vector1.insert(vector1.end(), vector2.begin(), vector2.end());
     이렇게 사용하면 vector1 뒤에 vector2가 붙는다.
     python에서 vector1.extend(vector2)로 사용하는 것과 같다.
2. algorithm 라이브러리
   • reverse(vector1.begin(), vector1.end());
     이렇게 사용하면 역순으로 바뀐다.
     python에서 vector1.reverse() 로 사용하는 것과 같다.

 

전체 코드

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

bool check_subvector(int length, vector<int> key, vector<int> rev_key, vector<int> sub_v)
{
    for (int i = 0; i + length < key.size(); i++)
    {
        if (vector<int>(key.begin()+i, key.begin()+i+length) == sub_v)
            return true;
        if (vector<int>(rev_key.begin()+i, rev_key.begin()+i+length) == sub_v)
            return true;
    }
    return false;
}

string vectorToString(vector<int> v)
{
    string ret = "";
    for (auto i:v)
        ret += to_string(i) + " ";
    return ret;
}

char rev_char(int i)
{
    switch (i)
    {
        case 1:   return 3;
        case 2:   return 4;
        case 3:   return 1;
        case 4:   return 2;
        default:    return i;
    }

}
vector<int> reverse_vector(vector<int> s)
{
    vector<int> new_v;
    reverse(s.begin(), s.end());
    for (auto item: s)
        new_v.push_back(rev_char(item));
    return new_v;
}

int main()
{
    // 1 init
    int length, N;
    vector<int> key, rev_key;
    vector<string> answer;

    // 2 algorithm
    cin >> length;
    for (int i = 0; i < length; i++)
    {
        int tmp;
        cin >> tmp;
        key.push_back(tmp);
    }
    key.insert(key.end(), key.begin(), key.end());  // key = orig_key * 2
    rev_key = reverse_vector(key);                  // 

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        vector<int> tmp;                            // for input
        for (int j = 0; j < length; j++)
        {
            int tmp_i;
            cin >> tmp_i;
            tmp.push_back(tmp_i);
        }

        if (check_subvector(length, key, rev_key, tmp))
        {
            answer.push_back(vectorToString(tmp));
        }
    }

    // 3 answer
    cout << answer.size() << endl;
    for (auto st: answer)
    {
        cout << st << endl;
    }
    return 0;
}