BOJ 21608 : 상어 초등학교 (삼성 SW TEST A형)

www.acmicpc.net/workbook/view/1152 (A형 문제집)

www.acmicpc.net/problem/21608

시뮬레이션 문제는 그대로 구현하면 된다.

학생 구조체 PEOPLE은 학생의 번호와 좋아하는 사람을 저장해야 한다.

학생은 N * N이므로 love 배열에 love[좋아하는 사람의 번호] = 1 로 표시하도록 하자.

그리고 좌표 (r, c)를 저장할 배열 spot이 필요하다.

#define MAX (20 + 5)

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

PEOPLE people[MAX * MAX];

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

RC spot[MAX * MAX];

MAP 주변을 -1로 만들어주고, (1, 1)부터 (N, N)까지 0으로 만든다.
그리고 people 배열에는 학생 번호, 좋아하는 사람을 check하도록 입력을 받는다.

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);
		
		people[i].index = num;
		people[i].love[one] = 1;
		people[i].love[two] = 1;
		people[i].love[three] = 1;
		people[i].love[four] = 1;
	}
}

simulate는 아래의 우선순위를 만족하는 대로 구현하면 된다.

1.을 만족하는 자리는 priority_one 배열에 담고, 모든 자리를 확인한 후, 자리가 1개라면 종료한다.

2.을 만족하는 자리는 priority_one 배열을 순서대로 확인하면서 priority_two 배열에 담고,

모든 자리를 확인한 후, priority_two[0]에 담긴 값이 정답이 된다.

2.을 만족하는 자리가 여러 개이더라도, (r, c)는 row와 column이 작은 값부터 탐색하기 때문에

priority_two에서 가장 먼저 담긴 값이 3.을 만족하게 된다.

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

priority_one은 아래의 과정으로 좌표를 담는다.

모든 좌표 (r, c)에 대해

1. MAP[r][c]가 0이 아닌 경우는 앞의 학생이 자리를 앉은 경우이므로 무시한다.

2. 빈칸인 경우, 4방향 탐색으로 MAP[nr][nc]의 값이 people[].love[]에 있는지 check하여 count한다.

3-1) max 값보다 크면, max를 count로 갱신하고, ocnt를 0으로 초기화하고, priority_one에 좌표를 담는다.

3-2) max 값과 같으면, priority_one 좌표에 추가로 담는다.

좋아하는 사람의 수가 근처에 많은 순대로 우선순위가 만들어지기 때문에

좌표 주변에 좋아하는 사람의 수가 기존보다 더 많은 경우, 기존의 좌표는 쓸모가 없어진다.

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 (people[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;
			}
		}
	}
}

priority_one에 좌표를 모두 담았다.

ocnt가 1인 경우는 우선순위가 결정되었으므로

MAP에 표시하고 해당하는 people의 번호에 좌표를 저장해두자. (추후 점수 계산을 위한 기록)

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

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

	continue;
}

priority_two는 one에서 좌표가 여러 개인 경우에 필요한 배열이다.

따라서 (1, 1)부터 (N, N)까지 모두 탐색하는 것이 아니라 priority_one에 저장된 좌표를 탐색한다.

이 때, priority_one이 row가 작은 순서대로, 그리고 column이 작은 순서대로 탐색하였기 때문에

priority_two에 가장 먼저 담긴 좌표가 2번 조건과 3번 조건의 우선순의를 모두 만족한다.

priority_two는 주변 좌표가 빈칸인 경우만 count하고 max와 비교하여 갱신하면 된다.

/* 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에 기록하고, spot에 저장하도록 하자.

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

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

이 과정을 모든 사람(p = 0 ~ N * N)에 대해 반복하면 MAP이 모두 채워진다.

MAP이 완성되었으므로, 문제에서 제시한대로 점수를 매기면 된다.

spot 배열에 people[].index에 해당하는 좌표를 저장하였으므로, 그 좌표를 기준으로 4방향 탐색을 한다.

4방향 탐색을 해서 좋아하는 사람의 수가 옆에 있는지 counting하여 sum에 점수를 누적하면 된다.

int sum = 0;
for (int p = 0; p < N * N; p++)
{
	int r, c;
	int index = people[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 (people[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;
}

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (20 + 5)

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

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

PEOPLE people[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);
		
		people[i].index = num;
		people[i].love[one] = 1;
		people[i].love[two] = 1;
		people[i].love[three] = 1;
		people[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 (people[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] = people[p].index;

			spot[people[p].index].r = priority_one[0].r;
			spot[people[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] = people[p].index;

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

int main(void)
{
	input();
	
	simulate();
	
	int sum = 0;
	for (int p = 0; p < N * N; p++)
	{
		int r, c;
		int index = people[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 (people[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;
}

실제 A형은 tc가 여러 개이므로, people 배열의 love 배열을 초기화하는 코드가 필요하다.

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 21610 : 마법사 상어와 비바라기 (삼성 SW TEST A형) (0)	2021.04.30
BOJ 21609 : 상어 중학교 (삼성 SW TEST A형) (0)	2021.04.29
BOJ 20058 : 마법사 상어와 파이어스톰 (삼성 SW TEST A형) (0)	2021.04.20
BOJ 20057 : 마법사 상어와 토네이도 (삼성 SW TEST A형) (0)	2021.04.16
BOJ 20056 : 마법사 상어와 파이어볼 (삼성 SW TEST A형) (0)	2021.04.13

피로물든딸기의 라이브러리

BOJ 21608 : 상어 초등학교 (삼성 SW TEST A형)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 21608 : 상어 초등학교 (삼성 SW TEST A형)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바