728x90
반응형
이 문제는 삼성 SW 기출 문제이고, simulation 문제이다.
1. 시작 점 (x, y)
2. 시작 방향 (direction)
struct point{
int x,y,direction;
};
n세대는 n - 1 세대 드래곤 커브 끝점을 기준으로 시계 방향으로 90도 회전시킨다음 끝점에 붙인 것이다.
그렇다면 점들의 위치는 어떤 방식으로 정해지는 건지 궁금하여 점이 변하는 방향을 따져봤다.
0: x좌표가 증가하는 방향 (→)
1: y좌표가 감소하는 방향 (↑)
2: x좌표가 감소하는 방향 (←)
3: y좌표가 증가하는 방향 (↓)
pair<int,int> direct[]={{1,0},{0,-1},{-1,0},{0,1}};
1세대
→ / ↑
0 / 1
2세대
→ ↑ / ← ↑
0 1 / 2 1
3세대
→ ↑ ← ↑ / ← ↓ ← ↑
0 1 2 1 / 2 3 2 1
4세대
→ ↑ ← ↑ ← ↓ ← ↑ / ← ↓ → ↓ ← ↓ ← ↑
0 1 2 1 2 3 2 1 / 2 3 0 3 2 3 2 1
각 세대를 살펴봤을 때, 회전 방향은 n - 1 세대의 회전방향을 역순으로 아래와 같이 회전한다는 것을 알 수 있다.
int rotationDirect[]={1,2,3,0};
따라서 회전할 때 역순으로 탐색하여 회전 방향을 설정 후 벡터에 저장하고,
벡터에 저장하기 전 벡터의 사이즈를 시작점으로 하여
순차적으로 탐색하면서 바로 전 정점에 대해 해당 회전 방향을 더하고
해당 정점에 대한 방문 여부를 체크한다.
그리고 세대가 증가 함에 따라 위를 반복한다.
void upgradeGeneration(point p, int generation){
int pgeneration = 0;
vector<point> pointVector;
point end;
end.x = p.x + direct[p.direction].first;
end.y = p.y + direct[p.direction].second;
end.direction = p.direction;
visitedPoint[end.x][end.y] = true;
pointVector.push_back(end);
while(pgeneration != generation){
int size = pointVector.size();
pgeneration++;
for(int i = size - 1; i >= 0; i--){
end.direction = rotationDirect[pointVector[i].direction];
pointVector.push_back(end);
}
for(int i = size; i < pointVector.size(); i++){
pointVector[i].x = pointVector[i - 1].x + direct[pointVector[i].direction].first;
pointVector[i].y = pointVector[i - 1].y + direct[pointVector[i].direction].second;
visitedPoint[pointVector[i].x][pointVector[i].y] = true;
}
}
}
그 후 체크된 방문 배열에 대해 정사각형인지 확인 후 정사각형이라면 answer를 증가시킨다.
void checkSquare(){
for(int i = 0; i < 101; i++){
for(int j = 0; j < 101; j++){
if(visitedPoint[i][j] == true && visitedPoint[i + 1][j + 1] == true && visitedPoint[i+1][j] == true && visitedPoint[i][j + 1] == true){
answer++;
}
}
}
}
전체 코드는 이렇다.
//드래곤 커브
#include <iostream>
#include <vector>
using namespace std;
struct point{
int x,y,direction;
};
pair<int,int> direct[]={{1,0},{0,-1},{-1,0},{0,1}};
int rotationDirect[]={1,2,3,0};
bool visitedPoint[102][102];
int answer = 0;
void upgradeGeneration(point p, int generation){
int pgeneration = 0;
vector<point> pointVector;
point end;
end.x = p.x + direct[p.direction].first;
end.y = p.y + direct[p.direction].second;
end.direction = p.direction;
visitedPoint[end.x][end.y] = true;
pointVector.push_back(end);
while(pgeneration != generation){
int size = pointVector.size();
pgeneration++;
for(int i = size - 1; i >= 0; i--){
end.direction = rotationDirect[pointVector[i].direction];
pointVector.push_back(end);
}
for(int i = size; i < pointVector.size(); i++){
pointVector[i].x = pointVector[i - 1].x + direct[pointVector[i].direction].first;
pointVector[i].y = pointVector[i - 1].y + direct[pointVector[i].direction].second;
visitedPoint[pointVector[i].x][pointVector[i].y] = true;
}
}
}
void checkSquare(){
for(int i = 0; i < 101; i++){
for(int j = 0; j < 101; j++){
if(visitedPoint[i][j] == true && visitedPoint[i + 1][j + 1] == true && visitedPoint[i+1][j] == true && visitedPoint[i][j + 1] == true){
answer++;
}
}
}
}
int main(void){
int num;
cin >> num;
for(int i = 0; i < num; i++){
point p;
int generation;
cin >> p.x >> p.y >> p.direction >> generation;
visitedPoint[p.x][p.y] = true;
upgradeGeneration(p,generation);
}
checkSquare();
cout << answer;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 아기상어 (0) | 2020.12.28 |
---|---|
[algorithm] 백준 - 치킨배달 (0) | 2020.12.27 |
[algorithm] 백준 - 사다리 조작 (0) | 2020.12.25 |
[algorithm] 백준 - 감시 (0) | 2020.12.24 |
[algorithm] 백준 - 톱니바퀴 (0) | 2020.12.24 |