백준 온라인 저지에 수록되어있는 문제의 설명과 풀이 및 소스 코드를 작성한 글입니다.
💡 문제
https://www.acmicpc.net/problem/15685
💡 문제 설명
문제
드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.
1. 시작점
2. 시작 방향
3. 세대
0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.
1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.
2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)
3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.
즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.
크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.
입력
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)
입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.
방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.
- 0: x좌표가 증가하는 방향 (→)
- 1: y좌표가 감소하는 방향 (↑)
- 2: x좌표가 감소하는 방향 (←)
- 3: y좌표가 증가하는 방향 (↓)
출력
첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.
예제 입력 1
3 3 3 0 1 4 2 1 3 4 2 2 1예제 출력 1
4
예제 입력 2
4 3 3 0 1 4 2 1 3 4 2 2 1 2 7 3 4예제 출력 2
11
예제 입력 3
10 5 5 0 0 5 6 0 0 5 7 0 0 5 8 0 0 5 9 0 0 6 5 0 0 6 6 0 0 6 7 0 0 6 8 0 0 6 9 0 0예제 출력 3
8
예제 입력 4
4 50 50 0 10 50 50 1 10 50 50 2 10 50 50 3 10예제 출력 4
1992
힌트
예제 1
예제 2
💡 풀이
처음에는 좌표들을 어떻게 다 저장할지 몰라서 고생했는데 규칙성을 찾고나니 생각보다 간단하게 풀렸다. 본인은 드래곤 커브 그림을 0세대부터 차근차근 그려보다보니 규칙성을 찾을 수 있었다.
위의 그림은 (0, 0)에서 시작하고 시작 방향이 오른쪽인 1세대의 드래곤 커브이다. 0, 1, 2, 3은 각각 방향을 나타낸다. 0번 방향을 시계 방향으로 90도 회전하면 3번 방향이 된다. 하지만 우리가 저장해야할 최종 진행 방향은 180도 회전시킨 1번 방향이다.
위의 그림은 이어서 그린 (0, 0)에서 시작하고 시작 방향이 오른쪽인 2세대의 드래곤 커브이다. 0번 방향과 1번 방향을 시계 방향으로 90도 회전하면 0번과 3번 방향이 된다. 하지만 우리가 저장해야할 최종 진행 방향은 180도 회전시킨 2번과 1번 방향이다.
마지막으로 위의 그림은 똑같이 이어서 그린 (0, 0)에서 시작하고 시작 방향이 오른쪽인 3세대의 드래곤 커브이다. 0, 1, 2, 1번 방향을 시계 방향으로 90도 회전하면 0, 1, 0, 3번 방향이 된다. 하지만 우리가 저장해야할 최종 진행 방향은 180도 회전시킨 2, 3, 2, 1번 방향이다.
결국 규칙성은 k세대의 드래곤 커브의 진행 방향은 k-1세대의 드래곤 커브의 진행 방향에 k-1세대의 드래곤 커브의 진행 방향의 역순을 각각 반시계 방향으로 돌려준 것(1을 더하고 4로 나눈 나머지)을 이어붙인 것이 된다. 예를 들어, 현재 세대의 드래곤 커브의 진행 방향이 0 1 2 3이었다면 역순을 취하고(3 2 1 0), 반시계 방향으로 돌리고(0 3 2 1), 이를 이어붙인 0 1 2 3 + 0 3 2 1 이 다음 세대의 드래곤 커브 진행 방향이 된다.
💡 소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 점들을 구현하는 것보다는 방향을 저장하여 그것으로 좌표를 복원하면 훨씬 효율적으로 구현 가능
bool loc[101][101]; // x, y 좌표 모두 0 ~ 100
// 동, 북, 서, 남
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
// 드래곤 커브의 이동방향을 모두 기록해놓는 함수
vector<int> dragon_curve(int x, int y, int d, int g) {
vector<int> ret = { d }; // 0세대
// g세대까지 기록
for (int i = 1; i <= g; i++) {
vector<int> temp(ret); // 전 세대 복사
reverse(temp.begin(), temp.end()); // 방향을 정반대로 변환
for (int &t : temp) {
t = (t + 1) % 4; // 방향을 반시계 방향으로 90도 회전
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
int main() {
int n; // 드래곤 커브의 개수
cin >> n;
while (n--) {
int x, y, d, g; // 시작 좌표, 시작 방향, 세대
cin >> x >> y >> d >> g;
vector<int> dir = dragon_curve(x, y, d, g);
loc[x][y] = true;
for (int d : dir) {
x += dx[d];
y += dy[d];
loc[x][y] = true;
}
}
int ans = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
// 4개의 좌표가 모두 TRUE인 경우
if (loc[i][j] && loc[i + 1][j] && loc[i][j + 1] && loc[i + 1][j + 1]) {
ans += 1;
}
}
}
cout << ans << '\n';
return 0;
}💡 풀이 후기
처음에 좌표를 일일이 전부 저장하려다가 코드가 굉장히 길어졌지만 이내 포기하고 방향만으로 좌표를 저장하였더니 코드가 생각보다 굉장히 짧아졌다.
시뮬레이션 문제는 대부분 첫 단추를 잘못 끼우면 머리와 몸이 굉장히 고생하는 것 같다. 좌표를 다루는 문제에서 방향을 저장하면 진행 좌표를 전부 복원해낼 수 있다는 것을 명심해야겠다.
