[백준 15685] 드래곤 커브

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

그림을 그려서 풀면 당최 무슨 말인지 이해가 안가는 문제였다.

첫 번째로 주의할 점은 다른 문제들과 다르게 (col, row)라는 점이다. 처음에 입력 받을 때 y,x로 받아야 한다.

 

다음으로 구현

주어진 예시에서 방향에 주목하여 문제를 풀어야 한다. 다음 그림은 예시에서 설명된 드래곤 커브의 방향을 세대 별로 색을 달리하여 나타낸 것이다. 

다음 세대에 오는 커브는 이전 세대의 커브 배열을 거꾸로 순회하며 시계반대방향으로 90도 회전한 방향을 추가하는 것을 확인할 수 있다.

시계 반대방향 90도 회전은 0 -> 1 -> 2 -> 3 -> 0 이 되는 순서이다.

 

드래곤 커브에 위치한 1x1 정사각형의 개수를 구하기 위해 좌표값을 map에 표시한다. 방향에 따라 x,y를 이동하며 map에 체크해준다.

 

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

using namespace std;

bool map[101][101] = {
    false,
};

int dr[] = {0, -1, 0, 1};
int dc[] = {1, 0, -1, 0};

vector<int> dragon;
int t, x, y, d, g;

int main(void)
{
  scanf("%d", &t);
  while (t--)
  {
    dragon.clear();
    scanf("%d%d%d%d", &y, &x, &d, &g);
    map[x][y] = true;
    x += dr[d], y += dc[d];
    map[x][y] = true;

    dragon.push_back(d);
    for (int i = 1; i <= g; i++)
    {
      int last = dragon.size() - 1;
      for (int j = last; j > -1; j--)
      {
        int nd = (dragon[j] + 1) % 4;
        x += dr[nd];
        y += dc[nd];
        map[x][y] = true;

        dragon.push_back(nd);
      }
    }
  }

  int res = 0;
  for (int i = 0; i <= 99; i++)
  {
    for (int j = 0; j <= 99; j++)
    {
      if (map[i][j] == true && map[i + 1][j] == true &&
          map[i][j + 1] == true && map[i + 1][j + 1] == true)
      {
        res++;
      }
    }
  }

  printf("%d\n", res);
  return 0;
}