[ 삼성 SW역량 평가 15685 ] 드래곤 커브 (C++)

[ 난이도 ]

★★☆

 

[ 문제 링크 ]

https://www.acmicpc.net/problem/15685

 

[ 문제 풀이 ]

복잡하면서도 간단한 시뮬레이션 문제이다.

 

우선 드래곤 커브의 세대가 늘어남에 따라 어떤 식으로 규칙이 생기는지 파악을 하여야 한다.

 

 

세대별 그림

그림과 같은경우 방향을 따져보면

0세대 : 0

1세대 : 0 1

2세대 : 0 1 2 1

3세대 : 0 1 2 1 2 3 2 1 과 같이 표시가 된다.

전 세대의 마지막 원소부터 대칭을 하고 1을 더한 후 4로 나눈 몫이 다음 세대 방향과 같다.

 

따라서 이 문제를 풀기위해

1. 해당 드래곤의 방향과 세대를 통해 이동할 방향을 모두 구해놓고

2. 드래곤이 방문한 지점을 체크해준뒤

3. 마지막으로 (0,0)부터 맵 끝까지 4각형으로 방문된 기록이 있으면 정답을 늘려준다.

 

[ 소스 코드 ]

// 헤더파일을 불러옵니다.
#include <iostream>
#include <vector>
using namespace std;
// 맵의 최대크기는 0 ~ 100 까지입니다.
#define Max_Size 101
 
// Dragon : 드래곤의 x,y,d,g를 담는 벡터
vector<pair<pair<int,int>, pair<int, int>>> Dragon;
// Direction : 해당 드래곤의 이동경로를 나타네는 벡터
vector<int> Direction;
 
// Visit : 드래곤이 방문한 이력이 있는지 유무를 알려줌
int Visit[Max_Size][Max_Size];
 
// N : 드래곤의 수
int N;
 
// 각각 →,↑,←,↓ 방향임
int dx[4] = {1,0,-1,0 };
int dy[4] = {0,-1,0,1 };
 
// ans : 정답을 나타내는 변수
int ans = 0;
 
// 입력을 받아오는 함수
void Load_Input()
{
    cin >> N;
    // 드래곤의 수만큼 벡터에 넣어줌
    for (int i = 0; i < N; ++i)
    {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        //각각 x좌표 y좌표 방향 d, 세대 g를 넣어줌
        Dragon.push_back(make_pair(make_pair(x, y), make_pair(d, g)));
    }
}
 
// 드래곤의 방향 d와 세대 g를 받아와서 움직여야 할 경로를 벡터에 모두 넣어줌
void Make_Direction(int d,int g)
{
    // 처음 방향을 넣고
    Direction.push_back(d);
    // 세대 수만큼 반복한다
    for (int i = 0; i < g; ++i)
    {
        // 마지막에서 역순으로 +1씩 해주고 4의 나머지값을 취해줌
        for (int j = Direction.size() - 1; j >= 0; --j)
        {
            Direction.push_back((Direction.at(j) + 1) % 4);
        }
    }
}
 
// 벡터를 초기화 시켜주는역할
void Erase_Vector()
{
    //Direction 벡터가 빌때까지
    while (!Direction.empty())
    {
        // 요소를 하나씩 지워나간다.
        Direction.pop_back();
    }
}
 
// 정답을 체크 하는 함수
void Check()
{    
    for (int i = 0; i < 100; ++i)
    {
        for (int j = 0; j < 100; ++j)
        {    
            // 0,0부터 시작해서 다음과 같이 방문 기록이 사각형이면 정답을 늘려줌
            if (Visit[i][j] == 1 && Visit[i][j + 1] == 1 && Visit[i + 1][j] == 1 && Visit[i + 1][j + 1] == 1)
            {
                ans++;
            }
        }
    }
}
 
// 드래곤을 만드는 함수 x,y,d,g를 매개변수로 받음.
void Make_Dragon(int x, int y, int d, int g)
{
    // x,y 좌표에 방문표시
    Visit[y][x] = 1;
    int nx = x;
    int ny = y;
 
    // 해당 드래곤의 경로를 만들어줌
    Make_Direction(d, g);
 
    // 경로벡터의 명령 횟수만큼 실행함.
    for (int i = 0; i < (int)Direction.size(); ++i)
    {
        // 새로운 위치로 이동
        nx = nx + dx[Direction.at(i)];
        ny = ny + dy[Direction.at(i)];
        // 새로운 위치 방문 표시
        Visit[ny][nx] = 1;
    }
    // 해당 드래곤이 끝나면 다음 드래곤을 위해 경로정보 벡터를 초기화 시켜줌
    Erase_Vector();
}
 
// 문제를 해결하는 함수
void Solve()
{
    // 각각 좌표와 방향 세대를 받는 변수
    int X, Y, D, G;
    // 드래곤의 수만큼 반복
    for (int i = 0; i < (int)Dragon.size(); ++i)
    {
        X = Dragon.at(i).first.first;
        Y = Dragon.at(i).first.second;
        D = Dragon.at(i).second.first;
        G = Dragon.at(i).second.second;
 
        Make_Dragon(X,Y,D,G);
    }
    // 드래곤을 수만큼 반복후 정답 체크
    Check();
}
int main()
{
    // 입력을 받아오고
    Load_Input();
    // 문제를 해결하고
    Solve();
    // 정답을 출력합니다.
    cout << ans;
    // 시스템을 정상종료합니다.
    return 0;
}