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

2641번: 다각형그리기

모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로

www.acmicpc.net

문제 요약

처음 주어지는 모양수열로 만들어진 도형과 같은 도형이 나오는 수열을 찾는 문제이다.
모양수열은 방향을 가리키는 숫자 (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에서 만들어진 것에 대해 입력이 부분 수열인지만 확인하면 된다.
- 들어온 입력이 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에서 부분 수열을 찾을수 없으므로 같은 도형이 아니다.(물론 이 입력은 도형이 만들어지지 않는다)
- 확인하는 알고리즘은 모든 길이를 확인하는 방식으로 만들었다.

새로 알게된 것

vector 라이브러리
- vector1.insert(vector1.end(), vector2.begin(), vector2.end());
  이렇게 사용하면 vector1 뒤에 vector2가 붙는다.
  python에서 vector1.extend(vector2)로 사용하는 것과 같다.
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;
}