예술성

Simulation, BFS

평균 : 180'

---

sol : 2:25:59

• 수행 시간 : 13ms
• 메모리 : 3MB

Learnings

• 설계 시간을 좀 더 여유있게 갖자.
• 쉽게 접근할 수 있었는데 너무 어렵게 풀었다.
• 자료 구조 선택 기준을 명확히 알아놓자.

  - vector
      - 키가 연속 정수일 경우, 최대 크기를 미리 알거나, 상한이 작은 경우
      - 접근이 빈번한 경우(수십만 ~ 수천만번)
      - 성능이 중요한 경우(캐시 친화적)
  - unordered_map
  	- 키가 연속이 아닌 경우
      - 등장한 키만 저장해서 메모리를 아끼고 싶은 경우
      - 최대 키 범위를 미리 잡기 어려운 경우
      - 접근 빈도가 그렇게 극단적으로 높지 않은 경우
      ex) (i, j)좌표를 키로 쓰거나, id가 10^9인데 실제 사용은 몇 천 개일 때.
  - array
  	- 크기 상한이 컴파일 타임 상수로 확정 가능한 경우
     - 초고속이 중요한 경우 (오버헤드 최소)
      - 대회, 코테에서 간단하게 쓰고 싶은 경우
      - 2D처럼 고정 격자가 명확한 경우

• 그래프 이론을 접목해서 푼 점은 나름 도전적이었고, 좋은 경험.

#include <iostream>
#include <unordered_map>
#include <utility>
#include <queue>
#include <tuple>

#define MAX_N 29
#define MAX_ADJ 900

using namespace std;

int n;
int grid[MAX_N][MAX_N];
long long score;
int groupId;
int squareLength;

int groupGrid[MAX_N][MAX_N];
int adjacent[MAX_ADJ][MAX_ADJ];
bool visited[MAX_N][MAX_N];
int tempGrid[MAX_N][MAX_N];
unordered_map<int, pair<int, int>> g;

int dis[4] = { 1, 0, -1, 0 };
int djs[4] = { 0, 1, 0, -1 };

void Debug(int area[MAX_N][MAX_N]) {
	cout << endl;
	cout << "DEBUG" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << area[i][j] << ' ';
		}
		cout << endl;;
	}
	cout << "DEBUG END" << endl << endl;;
}

void initGrid(int area[MAX_N][MAX_N]) {
	for (int i = 0; i < MAX_N; i++) {
		for (int j = 0; j < MAX_N; j++) {
			area[i][j] = 0;
		}
	}
}

void initAdj() {
	for (int i = 0; i < MAX_ADJ; i++) {
		for (int j = 0; j < MAX_ADJ; j++) {
			adjacent[i][j] = 0;
		}
	}
}

void initVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = false;
		}
	}
}

void GetGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
		}
	}
}

bool Inbound(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

void MakeGroupBfs(int i, int j) {
	queue<pair<int, int>> q;
	q.push(make_pair(i, j));
	g[groupId] = { grid[i][j], 1 };
	groupGrid[i][j] = groupId;
	int cnum = grid[i][j];

	while (!q.empty()) {
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + dis[d];
			int nj = cj + djs[d];

			if (Inbound(ni, nj) && groupGrid[ni][nj] == 0 && grid[ni][nj] == cnum) {
				q.push(make_pair(ni, nj));
				groupGrid[ni][nj] = groupId;
				g[groupId].second++;
			}
		}
	}
	// DEBUG
	//cout << "gId : " << groupId << " | num :  " << g[groupId].first << " | area : " << g[groupId].second << endl;
}

void FindAdjacentBfs(int i, int j) {
	queue<pair<int, int>> q;
	q.push(make_pair(i, j));
	visited[i][j] = true;

	while (!q.empty()) {
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + dis[d];
			int nj = cj + djs[d];

			if (Inbound(ni, nj) && !visited[ni][nj] && groupGrid[ni][nj] == groupId) {
				q.push(make_pair(ni, nj));
				visited[ni][nj] = true;
			}
			else if (Inbound(ni, nj) && !visited[ni][nj] && groupGrid[ni][nj] != groupId) {
				adjacent[groupId - 1][groupGrid[ni][nj] - 1]++;
			}
		}
	}
}

void MakeGroup() {
	groupId = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (groupGrid[i][j] == 0) {
				initVisited();
				MakeGroupBfs(i, j);
				groupId++;
			}
		}
	}
	// DEBUG
	//cout << "groupGrid";
	//Debug(groupGrid);
}

void FindAdjacent() {
	initVisited();
	initAdj();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				groupId = groupGrid[i][j];
				FindAdjacentBfs(i, j);
			}
		}
	}
	// DEBUG
	//cout << "adjacent";
	//Debug(adjacent);
}

void GetScore() {
	for (int i = 0; i < MAX_ADJ; i++) {
		for (int j = 0; j < MAX_ADJ; j++) {
			if (adjacent[i][j] != 0) {
				score += (g[i + 1].second + g[j + 1].second) * g[i + 1].first * g[j + 1].first * adjacent[i][j];
			}
		}
	}
}

void Evaluate() {
	initGrid(groupGrid);
	initAdj();

	// 그룹 번호와 실제 grid 번호 연동 방식은 unordered_map<int, pair<int, int>> g에서 g[그룹 번호].first로 확인 가능.
	// 1번째 BFS - 각 그룹별 넓이, 해당 영역 숫자, 그룹 번호로 bfs_map 구성.
	MakeGroup();

	// 2번째 BFS - 2차원 adjacent 배열에 서로 맞닿아 있는 그룹별 변의 수 저장용.
	FindAdjacent();

	// 점수 계산
	GetScore();
}


// Rotate
void CrossRotate() {
	for (int i = 0; i < n; i++) {
		tempGrid[n / 2][i] = grid[i][n / 2];
	}

	for (int j = 0; j < n; j++) {
		tempGrid[n - j - 1][n / 2] = grid[n / 2][j];
	}
}

void SquarePartRotate(int si, int sj) {
	for (int i = 0; i < squareLength; i++) {
		for (int j = 0; j < squareLength; j++) {
			tempGrid[si + i][sj + j] = grid[si + squareLength - j - 1][sj + i];
		}
	}
}

void Duplicate() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			grid[i][j] = tempGrid[i][j];
		}
	}
}

void SquareRotate() {
	squareLength = n / 2;
	// 1 사분면
	SquarePartRotate(0, n / 2 + 1);
	// 2 사분면
	SquarePartRotate(0, 0);
	// 3 사분면
	SquarePartRotate(n / 2 + 1, 0);
	// 4 사분면
	SquarePartRotate(n / 2 + 1, n / 2 + 1);

	// 회전맵 복제
	Duplicate();
}

void Rotate() {
	// 십자 모양 회전
	CrossRotate();
	// 나머지 회전
	SquareRotate();

	//Deboug
	//cout << "After Rotate";
	//Debug(grid);
}

int main() {
	cin >> n;

	// 초기 grid 설정
	GetGrid();

	// 초기 예술성 평가
	Evaluate();

	// 총 3번의 회전과 평가
	for (int turn = 1; turn <= 3; turn++) {
		Rotate();
		Evaluate();
	}

	// 종합 점수 발표
	cout << score;

	return 0;
}