코드트리 고대 문명 유적 탐사 (C++)

2024 상반기 삼성 코딩테스트 오전 1번 문제입니다. 어렵지 않게 구현할 수 있습니다.

 

	#include <bits/stdc++.h>
	#define endl '\n'
	#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll, ll> pll;
	typedef tuple<int,int,int> tiii;
	const int INF=1e9+1;
	int dx[]={1,0,-1,0};
	int dy[]={0,1,0,-1};
	bool spot_cmp(pii a, pii b) {
	// 빈 공간 채우기 위한 좌표 정렬
	if(a.second==b.second) return a.first>b.first;
	return a.second<b.second;
	}
	vector<vector<int>> rotate(pii center, int t, vector<vector<int>> board) {
	// center 기준 3x3 회전
	// 다른 위치에서도 같은 함수가 적용되어야 하므로 board 복사
	vector<vector<int>> v(3,vector<int>(3)), v2(3,vector<int>(3));
	for(int i=0;i<=2;i++) for(int j=0;j<=2;j++) v[i][j]=board[center.first-1+i][center.second-1+j];
	while(t--) {
	// rotate
	for(int i=0;i<=2;i++) {
	for(int j=0;j<=2;j++) v2[j][2-i]=v[i][j];
	}
	// copy
	for(int i=0;i<=2;i++) {
	for(int j=0;j<=2;j++) v[i][j]=v2[i][j];
	}
	}
	// copy to board
	for(int i=0;i<=2;i++) {
	for(int j=0;j<=2;j++) board[center.first-1+i][center.second-1+j]=v[i][j];
	}
	return board;
	}
	int connected(vector<vector<int>>& board) {
	// 연결된 유물 제거
	int total=0;
	vector<vector<int>> visit(5,vector<int>(5));
	for(int i=0;i<5;i++) {
	for(int j=0;j<5;j++) {
	if(visit[i][j]) continue;
	queue<pii> q;
	q.push({i,j});
	visit[i][j]=1;
	vector<pii> v={{i,j}};
	while(!q.empty()) {
	auto [x,y]=q.front();
	q.pop();
	for(int k=0;k<4;k++) {
	int nx=x+dx[k], ny=y+dy[k];
	if(nx>=0 && nx<5 && ny>=0 && ny<5 && !visit[nx][ny] && board[nx][ny]==board[i][j]) {
	q.push({nx,ny});
	visit[nx][ny]=1;
	v.push_back({nx,ny});
	}
	}
	}
	if(v.size()>=3) {
	total+=v.size();
	for(auto it : v) board[it.first][it.second]=0;
	}
	}
	}
	return total;
	}
	void fill_blank(vector<vector<int>>& board, queue<int>& q) {
	// 빈 공간에 조각으로 채우는 함수
	vector<pii> t;
	for(int i=0;i<5;i++) {
	for(int j=0;j<5;j++) {
	if(!board[i][j]) t.push_back({i,j});
	}
	}
	sort(t.begin(),t.end(),spot_cmp); // 좌표 정렬
	int k=t.size(), ids=0;
	while(k--) {
	int x=q.front(); q.pop();
	board[t[ids].first][t[ids].second]=x;
	ids++;
	}
	}
	int foo(vector<vector<int>>& board) {
	// 회전 후 유물 제거
	vector<vector<int>> v, vv;
	for(int t=1;t<=3;t++) {
	for(int i=1;i<=3;i++) {
	for(int j=1;j<=3;j++) {
	v=rotate({i,j},t,board);
	int a=connected(v);
	vv.push_back({-a,t,j,i}); // 유물 가치 최대화, 나머지 최소화
	}
	}
	}
	sort(vv.begin(),vv.end());
	board=rotate({vv[0][3],vv[0][2]},vv[0][1],board);
	int score=connected(board);
	return score;
	}
	bool blank_checker(vector<vector<int>>& board) {
	for(auto v : board) {
	for(auto it : v) {
	if(!it) return true;
	}
	}
	return false;
	}
	int main() {
	fastio
	freopen("input.txt","r",stdin);
	int K, M; cin>>K>>M;
	vector<vector<int>> board(5,vector<int>(5));
	for(int i=0;i<5;i++) {
	for(int j=0;j<5;j++) cin>>board[i][j];
	}
	queue<int> q;
	while(M--) {
	int x; cin>>x;
	q.push(x);
	}
	vector<int> scores;
	while(K--) {
	int score=foo(board);
	if(!score) break;
	while(blank_checker(board)) {
	fill_blank(board,q);
	score+=connected(board);
	}
	scores.push_back(score);
	}
	for(auto it : scores) cout<<it<<' ';
	return 0;
	}

view raw codetree_finder.cpp hosted with ❤ by GitHub