[코드트리] 놀이기구 탑승 (삼성 SW 역량테스트 2021 상반기 오전 1번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/go-on-the-rides

이후 설명 및 입/출력은 링크 참고

 

놀이기구 탑승 문제 풀이는 BOJ 21608 : 상어 초등학교와 같다.

#include <stdio.h>

#define MAX (20 + 5)

int T;
int N;
int MAP[MAX][MAX];

typedef struct st1
{
	int index;
	int love[MAX * MAX];
}STUDENT;

STUDENT student[MAX * MAX];

typedef struct st2
{
	int r;
	int c;
}RC;

RC spot[MAX * MAX];

void input()
{
	scanf("%d", &N);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = -1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			MAP[r][c] = 0;

	for (int i = 0; i < N * N; i++)
	{
		int num, one, two, three, four;

		scanf("%d %d %d %d %d", &num, &one, &two, &three, &four);

		student[i].index = num;
		student[i].love[one] = 1;
		student[i].love[two] = 1;
		student[i].love[three] = 1;
		student[i].love[four] = 1;
	}
}

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void simulate()
{
	RC priority_one[MAX * MAX] = { 0 };
	RC priority_two[MAX * MAX] = { 0 };
	int ocnt, tcnt; /* priority_one, two의 counter index */
	int max;

	for (int p = 0; p < N * N; p++)
	{
		//output();
		ocnt = tcnt = 0;
		max = -1;

		/* 1) 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. */
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c] != 0) continue;

				int count = 0;
				int nr, nc;
				for (int dir = 0; dir < 4; dir++)
				{
					nr = r + dr[dir];
					nc = c + dc[dir];

					if (MAP[nr][nc] == -1) continue;

					if (student[p].love[MAP[nr][nc]] == 1) count++;
				}

				if (max <= count)
				{
					if (max < count)
					{
						max = count;
						ocnt = 0;
						priority_one[ocnt].r = r;
						priority_one[ocnt++].c = c;
					}
					else
					{
						priority_one[ocnt].r = r;
						priority_one[ocnt++].c = c;
					}
				}
			}
		}

		if (ocnt == 1)
		{
			MAP[priority_one[0].r][priority_one[0].c] = student[p].index;

			spot[student[p].index].r = priority_one[0].r;
			spot[student[p].index].c = priority_one[0].c;

			continue;
		}


		/* 2) 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. */
		max = -1;
		for (int o = 0; o < ocnt; o++)
		{
			int count = 0;
			int nr, nc;
			for (int dir = 0; dir < 4; dir++)
			{
				nr = priority_one[o].r + dr[dir];
				nc = priority_one[o].c + dc[dir];

				if (MAP[nr][nc] == 0) count++;
			}

			if (max <= count)
			{
				if (max < count)
				{
					max = count;
					tcnt = 0;
					priority_two[tcnt].r = priority_one[o].r;
					priority_two[tcnt++].c = priority_one[o].c;
				}
				else
				{
					priority_two[tcnt].r = priority_one[o].r;
					priority_two[tcnt++].c = priority_one[o].c;
				}
			}
		}

		MAP[priority_two[0].r][priority_two[0].c] = student[p].index;

		spot[student[p].index].r = priority_two[0].r;
		spot[student[p].index].c = priority_two[0].c;
	}
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		simulate();

		int sum = 0;
		for (int p = 0; p < N * N; p++)
		{
			int r, c;
			int index = student[p].index;

			r = spot[index].r;
			c = spot[index].c;

			int count = 0;
			for (int dir = 0; dir < 4; dir++)
			{
				int nr, nc;

				nr = r + dr[dir];
				nc = c + dc[dir];

				if (MAP[nr][nc] == -1) continue;

				if (student[p].love[MAP[nr][nc]] == 1) count++;
			}

			if (count == 1) sum += 1;
			else if (count == 2) sum += 10;
			else if (count == 3) sum += 100;
			else if (count == 4) sum += 1000;
		}

		printf("%d\n", sum);
	}

	return 0;
}