[백준] 드래곤 커브

드래곤커브 (골4, 구현/시뮬레이션) : https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

 

구현 문제 중 특히 시뮬레이션 문제는 프라모델 조립하듯이 단계별로 나눠 풀면 된다.

큰 하나의 기능을 작은 세부적인 기능들로 나눈 다음, 조립해서 끼워 맞추듯 하나하나 구현한다음 합치면 된다.

 

 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int N, map[101][101] = {0};

// getCurveDots로 구한 드래곤 커브의 좌표들을 전부 저장하는 벡터.
vector<pair<int, int>> finalDots;

// 주어진 벡터 내의 점들을 (x, y) 기준으로 90도 시계 방향 회전시키는 함수.
// 좌표평면 상 점 (a,b)를 기준으로 (x, y)를 90도 시계 방향 회전 시 (y + a - b, -x + a + b)이지만,
// 문제에선 y가 아래로 내려갈수록 커지므로 (-y + a + b, x - a + b)가 됨.
void rotateDots(int x, int y, vector<pair<int, int>> &dots)
{
  for (int i = 0; dots.size() > i; i++)
  {
    swap(dots[i].first, dots[i].second);
    dots[i].first = -dots[i].first + x + y;
    dots[i].second = dots[i].second + y - x;
  }
}

// 방향과 세대, (x,y)를 기준으로, 드래곤 커브의 좌표를 구하여 finalDots에 저장하는 함수.
void getCurveDots(int x, int y, int direction, int generation)
{
  // 주어진 조건의 드래곤 커브 좌표를 저장하는 벡터.
  vector<pair<int, int>> dots;

  // 처음 시작 좌표(x,y) 를 저장한다.
  dots.push_back(make_pair(x, y));

  // 시작 방향에 따라, 두번째 좌표를 저장한다.
  switch (direction)
  {
  case 0:
    dots.push_back(make_pair(x + 1, y));
    break;
  case 1:
    dots.push_back(make_pair(x, y - 1));
    break;
  case 2:
    dots.push_back(make_pair(x - 1, y));
    break;
  case 3:
    dots.push_back(make_pair(x, y + 1));
    break;
  default:
    break;
  }

  // 세대에 따라 드래곤 커브 좌표들을 구한다.
  for (int nextGen = 0; generation > nextGen; nextGen++)
  {
    /* 
    마지막 점을 기준으로 회전하므로, 
    마지막 점을 제외한 좌표들을 복사하여 90도 회전한 다음 원래 벡터에 붙여준다.
    마지막 점은 항상 처음 (x, y)가 회전된 점이므로,
    배열을 복사할 시 역순으로 복사해 
    다음 세대의 마지막 점은 이전 세대의 마지막 점을 기준으로 (x, y)가 회전된 좌표로 유지시켜 준다.
    */
    pair<int, int> lastPoint = dots.back();
    vector<pair<int, int>> nextDots;

    nextDots.resize(dots.size() - 1);

    reverse_copy(dots.begin(), dots.end() - 1, nextDots.begin());

    rotateDots(lastPoint.first, lastPoint.second, nextDots);

    // 회전된 좌표들을 dots 벡터에다 붙이기.
    for (auto e : nextDots)
      dots.push_back(e);
  }

  // finalDots에 구한 드래곤 커브 좌표들을 저장한다.
  for (auto dot : dots)
  {
    finalDots.push_back(dot);
  }
}

// finalDots에 들어있는 좌표를 맵에 찍는 함수.
void fillMap()
{
  for (auto dot : finalDots)
    map[dot.first][dot.second] = 1;
}

// 맵에 찍힌 좌표로 정사각형 갯수 구하는 함수
int getSquareCnt()
{
  int cnt = 0;
  for (int i = 0; 100 > i; i++)
  {
    for (int j = 0; 100 > j; j++)
    {
      if (map[i][j] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j + 1] == 1)
        cnt++;
    }
  }
  return cnt;
}

int main(void)
{
  int x, y, d, g;

  scanf("%d", &N);

  /*
  1. for 문을 돌며, getCurveDots 함수를 호출하여 주어진 (x,y), 방향, 세대의 드래곤 커브 좌표를 구한다.
  이 좌표들은 마지막으로 finalDots 에 저장된다.
  2. fillMap 함수로 finalDots에 들어있는 좌표들을 맵에 찍는다.
  3. 정사각형 갯수를 구하는 함수를 호출하여 정사각형 갯수를 구한다.
  */

  for (int i = 0; N > i; i++)
  {
    scanf("%d %d %d %d", &x, &y, &d, &g);
    getCurveDots(x, y, d, g);
  }

  fillMap();

  cout << getSquareCnt() << '\n';

  return 0;
}