슬슬 골드 상위권 시뮬레이션 문제들도 익숙해지는 중이다.
이 문제는 하나만 정리하고 넘어가면 될것같다. 바로 배열의 90도 회전이다.
평소 문제를 푸는 상황에서 인덱스를 1부터 시작하지만, 회전 좌표를 고려하는 경우 이러한 습관이 매우 번거롭게 작용한다. 배열 회전이 필요한 경우 인덱스가 0부터 시작하는 배열을 설계하도록하자.
void Rotation_Clock(int x, int y, int Size) {
for(int i = 0; i < Size; i++)
for(int j = 0; j < Size; j++)
{
Tmp[x + j][y + Size - i - 1] = Map[x + i][y + i];
}
위와 같은 코드를 작성할 수 있다.
{x, y}
좌표는 회전하고자 하는 사각형의 좌측 상단 좌표다. Size
는 사각형 한 변의 길이다. 위의 공식은 부분, 전체를 통틀어 시작 좌표가 {0, 0}
에 해당하는 경우 작용하는 공식이다.
for(int i = 0; i < Size; i++)
for(int j = 0; j < Size; j++)
{
Tmp[x + Size - j - 1][y + i] = Map[x + i][y + j];
}
위와 같은 코드를 작성할 수 있다. 작용 조건은 시계방향 회전의 경우와 같다.
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int N;
int Visit[30][30];
pair<int, int> Map[30][30];
int Next[30][30];
//Label, Num
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int Area = 0;
vector<pair<int, int>> Cross;
vector<int> Temp;
int Ans = 0;
void Print() {
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
cout << Map[i][j].second << ' ';
}
cout << endl;
}
}
void Input() {
cin >> N;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
int num;
cin >> num;
Map[i][j] = {-1, num};
//초기 Label = -1;
}
}
void Land(int x, int y, int Label) {
queue<pair<int, int>> Q;
Q.push({x, y});
while(!Q.empty())
{
int px = Q.front().first;
int py = Q.front().second;
Q.pop();
for(int i = 0; i < 4; i++)
{
int nx = px + dx[i];
int ny = py + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue; //범위 초과
if(Visit[nx][ny] == 1 || Map[nx][ny].second != Map[x][y].second) continue; //방분 격자 or 다른 영역
Visit[nx][ny] = 1;
Map[nx][ny].first = Label;
Q.push({nx, ny});
}
}
}
void Art(int A, int B) {
//Label A
//Label B
int A_cnt = 0;
int B_cnt = 0;
int A_num = 0;
int B_num = 0;
int Cross_Line = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
//Label : A 기준으로 Cross 계산
if(Map[i][j].first == A)
{
A_cnt++;
A_num = Map[i][j].second;
//A칸을 발견하면 맞닿은 B칸을 카운팅한다.
for(int k = 0; k < 4; k++)
{
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if(Map[nx][ny].first == B) Cross_Line++;
}
}
else if(Map[i][j].first == B)
{
B_cnt++;
B_num = Map[i][j].second;
}
}
int Point = (A_cnt + B_cnt) * A_num * B_num * Cross_Line;
Ans += Point;
}
//2개 조합 구하기
void Dfs(int Count, int index) {
if(Count == 2)
{
Art(Temp[0], Temp[1]);
return;
}
//중복되지 않는 2개 조합
for(int i = index; i <= Area; i++)
{
Temp.push_back(i);
Dfs(Count + 1, i + 1);
Temp.pop_back();
}
}
//시계방향으로 90도 회전
void Rotation_Clock(int x, int y, int Size) {
for(int i = 0; i < Size; i++)
for(int j = 0; j < Size; j++)
{
Next[x + j][y + Size - i - 1] = Map[x + i][y + j].second;
}
}
//십자가 반시계 방향으로 90도 회전
void Rotation_Reverse(int Size) {
for(int i = 0; i < Cross.size(); i++)
{
int cx = Cross[i].first;
int cy = Cross[i].second;
Next[Size - cy - 1][cx] = Map[cx][cy].second;
}
}
void All_Rotation() {
int Size = N / 2;
Rotation_Clock(0, 0, Size);
Rotation_Clock(0, Size + 1, Size);
Rotation_Clock(Size + 1, 0, Size);
Rotation_Clock(Size + 1, Size + 1, Size);
//4개 사각형의 회전
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
if(i == N/2 || j == N/2)
{
Cross.push_back({i, j});
}
}
Rotation_Reverse(N);
//십자가 반시계 방향 회전
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
Map[i][j].first = -1;
Map[i][j].second = Next[i][j];
}
}
int main() {
Input();
int Time = 4;
while(Time--)
{
int Label = 1;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
if(Visit[i][j] == 0)
{
Visit[i][j] = 1;
Map[i][j].first = Label;
Land(i, j, Label);
Label++;
}
}
memset(Visit, 0, sizeof(Visit));
Area = Label - 1;
Dfs(0, 1);
//해당 회차의 포인트 더하기
All_Rotation();
memset(Next, 0, sizeof(Next));
}
cout << Ans;
}