By 정우석 in Problem Solving —

예술성 [2022-상반기 오후 2번 문제]

문제 링크

삼성 코딩테스트 기출 문제: 예술성 - 코드트리
주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.
코드트리

문제 설명

n*n의 격자가 있음. 1-10의 숫자가 써져있음.

같은 숫자로 인접한 경우 하나의 그룹으로 봄.

각 턴 당 점수를 얻는데, a,b라고 한다면

(a의 갯수 + b의 갯수) * a값 * b값 * 서로 맞닿아있는 변의 수를 점수로 침.

그 후, 회전을 진행하는데, 십자를 기준으로 십자는 반시계 방향으로 회전하고, 십자를 제외한 정사각형은 시계방향으로 90도 회전함.

4번의 턴 이후의 점수를 구하기.

해결 방법

회전십자 따로, 정사각형 따로 회전시켜줬음.

int calculate_art_val() {
	int ret = 0;
	for (int i = 0;i < group.size();i++) {
		for (int j = i+1;j < group.size();j++) {
			int adj_val = get_adjust_val(i, j);
			if (adj_val == 0) continue;
			int val = (group[i].cnt + group[j].cnt) * group[i].val * group[j].val * adj_val;
			ret += val;
		}
	}

	return ret;
}

int tmp_arr[30][30];

void rotate() {
	int ttmp[30][30];
	int N = n / 2;

	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			ttmp[i][j] = tmp_arr[N-j-1][i];
		}
	}

	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			tmp_arr[i][j] = ttmp[i][j];
		}
	}
}

void rotate_arr() {
	int N = n / 2;

	memset(tmp_arr, 0, sizeof(tmp_arr));
	// 1. tmp_arr에 넣기 -> 돌리기 -> 다시 복귀

	int dtx[4] = { 0,N+1,0,N+1 };
	int dty[4] = { 0,0,N+1,N+1 };

	for (int t = 0;t < 4;t++) {
		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) {
				tmp_arr[i][j] = arr[i+dtx[t]][j+dty[t]];
			}
		}
		rotate();
		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) {
				arr[i+dtx[t]][j+dty[t]] = tmp_arr[i][j];
			}
		}
	}

	int ttmp[2][31];
	for (int i = 0;i < n;i++) {
		ttmp[0][n-1-i] = arr[N][i];
	}
	
	for (int i = 0;i < n;i++) {
		ttmp[1][i] = arr[i][N];
	}

	for (int i = 0;i < n;i++) {
		arr[N][i] = ttmp[1][i];
		arr[i][N] = ttmp[0][i];
	}
}

점수 계산점수를 계산해주는데, 인접한 변을 계산하기 위해서 BFS를 사용하여 인접한 값들을 중복으로 세줬음.

int adjust_visited[31][31];
int get_adjust_val(int t1, int t2) {
	int v1, v2;
	v1 = t1+1; v2 = t2+1;

	memset(adjust_visited, 0, sizeof(adjust_visited));
	int x, y;
	x = group[t1].x, y = group[t1].y;

	queue<pair<int, int>> que;
	adjust_visited[x][y] = 1;

	int cx, cy, nx, ny;
	int ret_val = 0;
	que.push({ x,y });
	while (!que.empty()) {
		tie(cx, cy) = que.front();
		que.pop();

		for (int i = 0;i < 4;i++) {
			nx = cx + dx[i], ny = cy + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (adjust_visited[nx][ny] != 0) continue;
			if (visited[nx][ny] == v1) {
				// 본인인 경우
				adjust_visited[nx][ny] = 1;
				que.push({ nx,ny });
			}
			else if (visited[nx][ny] == v2) {
				ret_val++;
			}
		}
	}

	return ret_val;
}

int calculate_art_val() {
	int ret = 0;
	for (int i = 0;i < group.size();i++) {
		for (int j = i+1;j < group.size();j++) {
			int adj_val = get_adjust_val(i, j);
			if (adj_val == 0) continue;
			int val = (group[i].cnt + group[j].cnt) * group[i].val * group[j].val * adj_val;
			ret += val;
		}
	}

	return ret;
}

그룹 지어주기각 그룹의 첫번째 인덱스와 갯수, 그리고 값을 벡터에 저장해줌.

int set_group(int x,int y,int val) {
	int ret = 1;
	queue<pair<int, int>> que;
	que.push({ x,y });
	visited[x][y] = val;

	int cx, cy, nx, ny;
	while (!que.empty()) {
		tie(cx, cy) = que.front();
		que.pop();

		for (int i = 0;i < 4;i++) {
			nx = cx + dx[i], ny = cy + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (visited[nx][ny] != 0) continue;
			if (arr[nx][ny] != arr[x][y]) continue;
			visited[nx][ny] = val;
			ret++;
			que.push({ nx,ny });
		}
	}

	return ret;
}

void make_group() {
	memset(visited, 0, sizeof(visited));
	
	vector<_group> vec;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (visited[i][j] == 0) {
				_group tmp;
				int val = vec.size() + 1;
				tmp.cnt = set_group(i, j,val);
				tmp.x = i, tmp.y = j;
				tmp.val = arr[i][j];
				vec.push_back(tmp);
			}
		}
	}	
	group = vec;
}

전체 코드

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <cstring>

using namespace std;

typedef struct {
	int x, y;
	int cnt;
	int val;
}_group;

int n;
int arr[31][31];
int visited[31][31];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
vector<_group> group;

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

int set_group(int x,int y,int val) {
	int ret = 1;
	queue<pair<int, int>> que;
	que.push({ x,y });
	visited[x][y] = val;

	int cx, cy, nx, ny;
	while (!que.empty()) {
		tie(cx, cy) = que.front();
		que.pop();

		for (int i = 0;i < 4;i++) {
			nx = cx + dx[i], ny = cy + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (visited[nx][ny] != 0) continue;
			if (arr[nx][ny] != arr[x][y]) continue;
			visited[nx][ny] = val;
			ret++;
			que.push({ nx,ny });
		}
	}

	return ret;
}

void make_group() {
	memset(visited, 0, sizeof(visited));
	
	vector<_group> vec;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (visited[i][j] == 0) {
				_group tmp;
				int val = vec.size() + 1;
				tmp.cnt = set_group(i, j,val);
				tmp.x = i, tmp.y = j;
				tmp.val = arr[i][j];
				vec.push_back(tmp);
			}
		}
	}	
	group = vec;
}

int adjust_visited[31][31];
int get_adjust_val(int t1, int t2) {
	int v1, v2;
	v1 = t1+1; v2 = t2+1;

	memset(adjust_visited, 0, sizeof(adjust_visited));
	int x, y;
	x = group[t1].x, y = group[t1].y;

	queue<pair<int, int>> que;
	adjust_visited[x][y] = 1;

	int cx, cy, nx, ny;
	int ret_val = 0;
	que.push({ x,y });
	while (!que.empty()) {
		tie(cx, cy) = que.front();
		que.pop();

		for (int i = 0;i < 4;i++) {
			nx = cx + dx[i], ny = cy + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (adjust_visited[nx][ny] != 0) continue;
			if (visited[nx][ny] == v1) {
				// 본인인 경우
				adjust_visited[nx][ny] = 1;
				que.push({ nx,ny });
			}
			else if (visited[nx][ny] == v2) {
				ret_val++;
			}
		}
	}

	return ret_val;
}

int calculate_art_val() {
	int ret = 0;
	for (int i = 0;i < group.size();i++) {
		for (int j = i+1;j < group.size();j++) {
			int adj_val = get_adjust_val(i, j);
			if (adj_val == 0) continue;
			int val = (group[i].cnt + group[j].cnt) * group[i].val * group[j].val * adj_val;
			ret += val;
		}
	}

	return ret;
}

int tmp_arr[30][30];

void rotate() {
	int ttmp[30][30];
	int N = n / 2;

	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			ttmp[i][j] = tmp_arr[N-j-1][i];
		}
	}

	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			tmp_arr[i][j] = ttmp[i][j];
		}
	}
}

void rotate_arr() {
	int N = n / 2;

	memset(tmp_arr, 0, sizeof(tmp_arr));
	// 1. tmp_arr에 넣기 -> 돌리기 -> 다시 복귀

	int dtx[4] = { 0,N+1,0,N+1 };
	int dty[4] = { 0,0,N+1,N+1 };

	for (int t = 0;t < 4;t++) {
		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) {
				tmp_arr[i][j] = arr[i+dtx[t]][j+dty[t]];
			}
		}
		rotate();
		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) {
				arr[i+dtx[t]][j+dty[t]] = tmp_arr[i][j];
			}
		}
	}

	int ttmp[2][31];
	for (int i = 0;i < n;i++) {
		ttmp[0][n-1-i] = arr[N][i];
	}
	
	for (int i = 0;i < n;i++) {
		ttmp[1][i] = arr[i][N];
	}

	for (int i = 0;i < n;i++) {
		arr[N][i] = ttmp[1][i];
		arr[i][N] = ttmp[0][i];
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

//	freopen("sample_input.txt", "r", stdin);

	input();

	int result = 0;

	for (int i = 0;i <= 3;i++) {ㄱ
		make_group();
		result += calculate_art_val();
		rotate_arr();
	}
	cout << result;
}
Previous

꼬리잡기놀이 [2022-상반기 오후 1번 문제]

 Next

술래잡기 [2022-상반기 오전 1번 문제]

You might also like...