A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)
www.acmicpc.net/workbook/view/1152 (A형 문제집)
시뮬레이션 문제는 그대로 구현하면 된다.
학생 구조체 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 |
댓글