A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)
https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion
좌표를 관리하기 위한 구조체에 기절 상태, 탈락 여부, 점수 변수를 추가한다.
typedef struct st
{
int r;
int c;
int stun;
int dead;
int score;
}RC;
RC RUDOLF;
RC SANTA[30 + 5];
4방향 / 8방향 탐색을 위한 배열을 선언한다.
// 상, 우, 하, 좌
int dr4[] = { -1, 0, 1, 0 };
int dc4[] = { 0, 1, 0, -1 };
/* ←, ↖, ↑, ↗, →, ↘, ↓, ↙ */
int dr8[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int dc8[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
input은 다음과 같다.
void input()
{
scanf("%d %d %d %d %d", &N, &M, &P, &C, &D);
scanf("%d %d", &RUDOLF.r, &RUDOLF.c);
for (int p = 1; p <= P; p++)
{
int santaNum, r, c;
scanf("%d %d %d", &santaNum, &r, &c);
SANTA[santaNum].r = r;
SANTA[santaNum].c = c;
SANTA[santaNum].stun = SANTA[santaNum].dead = 0;
}
}
거리를 계산할 함수를 만들어둔다.
int getDistance(int r1, int c1, int r2, int c2)
{
return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}
2차원 배열 MAP을 만들어둔다.
setMap에서 빈 배열을 만들고 산타의 번호와 루돌프(= 99)를 적어둔다.
좌표는 기본적으로 SANTA 배열과 RUDOLF에 저장하고, 충돌 여부를 확인할 때, MAP을 갱신해서 검사한다.
#define MAX (50 + 5)
#define RUDOLF_NUMBER (99)
int MAP[MAX][MAX];
void setMap()
{
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
MAP[r][c] = 0;
for (int p = 1; p <= P; p++)
{
RC s = SANTA[p];
if (s.dead == 1) continue;
MAP[s.r][s.c] = p;
}
MAP[RUDOLF.r][RUDOLF.c] = RUDOLF_NUMBER;
}
main은 다음과 같다.
1) 루돌프의 움직임 → 충돌 처리 → 상호작용
2) 산타의 움직임 → 충돌 처리 → 상호작용
3) 게임 종료, 점수 계산
4) 산타가 모두 탈락한 경우 시뮬레이션 종료
int main()
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
for (int m = 0; m < M; m++)
{
// 루돌프의 움직임 → 충돌 처리 → 상호작용
moveRudolf();
// 산타의 움직임 → 충돌 처리 → 상호작용
moveSanta();
// 게임 종료, 점수 계산
scoreUp();
if (checkAllDeadSanta() == 1) break;
}
for (int p = 1; p <= P; p++) printf("%d ", SANTA[p].score);
}
return 0;
}
루돌프의 움직임
루돌프의 움직임은 다음과 같다.
1) setMap으로 현재 MAP을 갱신한다.
2) getNearSantaIndex로 문제에서 요구하는 조건을 만족하는 가장 가까운 산타의 번호를 찾는다.
3) getRudolfDirection으로 루돌프가 움직일 8방향 중 하나를 구한다.
4) 루돌프의 좌표를 갱신한다.
5) 해당되는 좌표에 산타가 있는 경우(MAP[nr][nc] != 0), 산타를 움직인다. (점수 추가)
6) 산타가 움직인 방향에 다른 산타가 있는 경우 상호작용한다.
void moveRudolf()
{
setMap();
int nearSantaIndex = getNearSantaIndex();
int rudolfDirection = getRudolfDirection(nearSantaIndex);
int nr, nc;
nr = RUDOLF.r + dr8[rudolfDirection];
nc = RUDOLF.c + dc8[rudolfDirection];
RUDOLF.r = nr;
RUDOLF.c = nc;
if (MAP[nr][nc] != 0) // 충돌 처리
{
int crashSantaIndex = MAP[nr][nc];
RC crashSanta = SANTA[crashSantaIndex];
int snr, snc;
snr = crashSanta.r + (dr8[rudolfDirection]) * C;
snc = crashSanta.c + (dc8[rudolfDirection]) * C;
// 외부로 나가는 경우
if (snr < 1 || snc < 1 || snr > N || snc > N) SANTA[crashSantaIndex].dead = 1;
else if (MAP[snr][snc] != 0) // 다른 산타가 있는 경우 (본인이 아닌 경우) 상호작용
{
int interSantaIndex = MAP[snr][snc];
interaction(interSantaIndex, rudolfDirection, 1);
}
SANTA[crashSantaIndex].r = snr;
SANTA[crashSantaIndex].c = snc;
SANTA[crashSantaIndex].stun = 2;
SANTA[crashSantaIndex].score += C;
}
}
가장 가까운 산타의 번호는 MAP에서 r이 큰 순서대로, c가 큰 순서대로 탐색하면 된다. (문제의 요구조건)
setMap에 의해 산타의 번호가 기록되어 있으므로, MAP[r][c]가 0이 아니고 루돌프가 아닌 곳을 찾아 거리를 계산한다.
int getNearSantaIndex()
{
int ret;
int minDistance = 0x7fff0000;
for (int r = N; r >= 1; r--)
{
for (int c = N; c >= 1; c--)
{
if (MAP[r][c] == 0 || MAP[r][c] == RUDOLF_NUMBER) continue;
int distance = getDistance(RUDOLF.r, RUDOLF.c, r, c);
if (distance < minDistance)
{
minDistance = distance;
ret = MAP[r][c];
}
}
}
return ret;
}
가장 가까운 산타의 번호를 찾았다면, 해당 번호로 루돌프가 움직일 방향을 계산할 수 있다.
문제에서 제시한 "거리"의 정의대로 가까워지는지 판단해야 한다.
여기서 루돌프를 임의로 8방향 움직여보고, 가장 가까워지는 거리를 찾았다.
int getRudolfDirection(int santaIndex)
{
int direction = -1;
int minDistance = 0x7fff0000;
RC santa = SANTA[santaIndex];
for (int i = 0; i < 8; i++)
{
int nr, nc;
nr = RUDOLF.r + dr8[i];
nc = RUDOLF.c + dc8[i];
int distance = getDistance(nr, nc, santa.r, santa.c);
if (distance < minDistance)
{
minDistance = distance;
direction = i;
}
}
return direction;
}
위에서 구한 방향으로 루돌프를 움직인다.
int rudolfDirection = getRudolfDirection(nearSantaIndex);
int nr, nc;
nr = RUDOLF.r + dr8[rudolfDirection];
nc = RUDOLF.c + dc8[rudolfDirection];
RUDOLF.r = nr;
RUDOLF.c = nc;
해당되는 좌표가 MAP에서 0이 아니라면, 산타가 있는 경우다.
산타의 좌표에서 루돌프의 방향에 C를 곱한 값으로 산타를 이동시킨다.
외부로 나가는 경우 dead = 1로 처리한다.
또 다른 산타가 있는 경우는 상호작용을 하였다.
그리고 산타의 좌표를 갱신하고 기절 표시 = 2, 점수를 C만큼 증가한다.
if (MAP[nr][nc] != 0) // 충돌 처리
{
int crashSantaIndex = MAP[nr][nc];
RC crashSanta = SANTA[crashSantaIndex];
int snr, snc;
snr = crashSanta.r + (dr8[rudolfDirection]) * C;
snc = crashSanta.c + (dc8[rudolfDirection]) * C;
// 외부로 나가는 경우
if (snr < 1 || snc < 1 || snr > N || snc > N) SANTA[crashSantaIndex].dead = 1;
else if (MAP[snr][snc] != 0) // 다른 산타가 있는 경우 (본인이 아닌 경우) 상호작용
{
int interSantaIndex = MAP[snr][snc];
interaction(interSantaIndex, rudolfDirection, 1);
}
SANTA[crashSantaIndex].r = snr;
SANTA[crashSantaIndex].c = snc;
SANTA[crashSantaIndex].stun = 2;
SANTA[crashSantaIndex].score += C;
}
상호작용은 다음과 같다.
먼저 루돌프에 의한 상호작용은 8방향을 움직일 수 있고, 산타에 의한 상호작용은 4방향을 움직인다.
따라서 isRudolf 변수로 구분하여 dr8을 쓸지 dr4를 쓸지 경우를 나눠야 한다.
(interaction을 호출할 때, isRudolf가 1인 것을 알 수 있다.)
while 문에서 주어진 산타(santaIndex)에서 방향(direction)으로 연속된 산타를 candidate 배열에 추가한다.
그리고 candidate에 들어간 모든 산타를 한 칸 움직인다.
이때, 좌표가 벗어난 경우는 탈락 처리한다. (dead = 1)
void interaction(int santaIndex, int direction, int isRudolf)
{
RC startSanta = SANTA[santaIndex];
int candidate[30 + 5] = { 0 }; // 밀려날 산타들
int cnt = 0;
candidate[cnt++] = santaIndex;
int nr, nc;
nr = startSanta.r;
nc = startSanta.c;
while (1)
{
if (isRudolf == 1)
{
nr = nr + dr8[direction];
nc = nc + dc8[direction];
}
else
{
nr = nr + dr4[direction];
nc = nc + dc4[direction];
}
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (MAP[nr][nc] == 0) break;
candidate[cnt++] = MAP[nr][nc];
}
for (int i = 0; i < cnt; i++)
{
int index = candidate[i];
RC s = SANTA[index];
int snr, snc;
snr = s.r;
snc = s.c;
if (isRudolf == 1)
{
snr = snr + dr8[direction];
snc = snc + dc8[direction];
}
else
{
snr = snr + dr4[direction];
snc = snc + dc4[direction];
}
if (snr < 1 || snc < 1 || snr > N || snc > N)
{
SANTA[index].dead = 1;
continue;
}
SANTA[index].r = snr;
SANTA[index].c = snc;
}
}
산타의 움직임
탈락한 산타 (dead == 1)와 기절한 산타 (stun != 0)를 제외하고 움직인다.
루돌프에 의해 산타가 기절하는 경우, moveSanta에서 stun을 1 감소하고, 다음 턴에서 1 감소하게 된다.
(문제에서 k번째 턴에서 기절한 경우, k + 1번째 턴까지 기절한다고 명시되어 있다.)
void moveSanta()
{
for (int p = 1; p <= P; p++)
{
RC s = SANTA[p];
if (s.dead == 1) continue;
if (s.stun != 0)
{
SANTA[p].stun--;
continue;
}
moveEachSanta(p);
}
}
각 산타는 다음과 같이 움직인다.
1) setMap으로 현재 좌표를 갱신한다.
2) 루돌프와 가까워지는 방향을 찾는다.
ㄴ 움직일 수 있는 방향이 없다면 (direction = -1), 종료한다.
3) 산타의 좌표를 갱신한다.
4) 움직인 공간에 루돌프가 있다면, 방향을 바꿔서 D를 곱한만큼 이동한다. (changeDir로 방향 변경)
ㄴ 이때, 좌표를 벗어난다면 탈락 처리한다. (dead = 1)
5) 다른 산타가 있는 경우, 상호작용한다. (isRudolf = 0)
산타가 움직여서 루돌프에 부딪힌 경우는 stun = 1로 처리한다.
moveEachSanta가 호출되기 전에 stun-- 가 실행되었기 때문이다.
void moveEachSanta(int santaIndex)
{
setMap();
RC santa = SANTA[santaIndex];
int currentDistance = getDistance(RUDOLF.r, RUDOLF.c, santa.r, santa.c);
int minDistance = 0x7fff0000;
int direction = -1;
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = santa.r + dr4[i];
nc = santa.c + dc4[i];
int nextDistance = getDistance(RUDOLF.r, RUDOLF.c, nr, nc);
if (currentDistance < nextDistance) continue; // 멀어지는 방향
if (MAP[nr][nc] == RUDOLF_NUMBER)
{
minDistance = 1;
direction = i;
break;
}
if (MAP[nr][nc] != 0) continue; // 다른 산타가 있는 경우
if (nextDistance < minDistance)
{
minDistance = nextDistance;
direction = i;
}
}
// 움직일 수 있는 공간이 없는 경우 종료
if (direction == -1) return;
SANTA[santaIndex].r = santa.r + dr4[direction];
SANTA[santaIndex].c = santa.c + dc4[direction];
// 움직인 공간에 루돌프가 있는 경우
if (MAP[SANTA[santaIndex].r][SANTA[santaIndex].c] == RUDOLF_NUMBER)
{
SANTA[santaIndex].stun = 1;
int changeDir[4] = { 2, 3, 0, 1 };
int snr, snc;
direction = changeDir[direction];
snr = SANTA[santaIndex].r + dr4[direction] * D;
snc = SANTA[santaIndex].c + dc4[direction] * D;
SANTA[santaIndex].score += D;
if (snr < 1 || snc < 1 || snr > N || snc > N)
{
SANTA[santaIndex].dead = 1;
return;
}
SANTA[santaIndex].r = snr;
SANTA[santaIndex].c = snc;
if (MAP[snr][snc] != 0) // 다른 산타가 있는 경우 (본인은 아닌 경우)
{
int interSantaIndex = MAP[snr][snc];
if (interSantaIndex != santaIndex) interaction(interSantaIndex, direction, 0);
}
}
}
게임 종료 및 판단
산타를 순회하면서 탈락하지 않은 산타의 점수를 증가한다.
void scoreUp()
{
for (int p = 1; p <= P; p++)
{
if (SANTA[p].dead == 1) continue;
SANTA[p].score++;
}
}
모든 산타가 dead = 1인지 체크하는 함수를 만든다.
int checkAllDeadSanta()
{
for (int p = 1; p <= P; p++)
if (SANTA[p].dead == 0) return 0;
return 1;
}
전체 코드는 다음과 같다.
#include <stdio.h>
#define MAX (50 + 5)
#define RUDOLF_NUMBER (99)
int T;
int N, M, P, C, D;
int MAP[MAX][MAX];
typedef struct st
{
int r;
int c;
int stun;
int dead;
int score;
}RC;
RC RUDOLF;
RC SANTA[30 + 5];
// 상, 우, 하, 좌
int dr4[] = { -1, 0, 1, 0 };
int dc4[] = { 0, 1, 0, -1 };
/* ←, ↖, ↑, ↗, →, ↘, ↓, ↙ */
int dr8[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int dc8[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
void input()
{
scanf("%d %d %d %d %d", &N, &M, &P, &C, &D);
scanf("%d %d", &RUDOLF.r, &RUDOLF.c);
for (int p = 1; p <= P; p++)
{
int santaNum, r, c;
scanf("%d %d %d", &santaNum, &r, &c);
SANTA[santaNum].r = r;
SANTA[santaNum].c = c;
SANTA[santaNum].stun = SANTA[santaNum].dead = 0;
}
}
void printMap()
{
for (int p = 1; p <= P; p++)
{
RC s = SANTA[p];
printf("%d] (%d, %d) %d / %d / %d\n", p, s.r, s.c, s.stun, s.dead, s.score);
}
putchar('\n');
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
printf("%2d ", MAP[r][c]);
putchar('\n');
}
printf("==================================\n");
}
int getDistance(int r1, int c1, int r2, int c2)
{
return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}
void setMap()
{
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
MAP[r][c] = 0;
for (int p = 1; p <= P; p++)
{
RC s = SANTA[p];
if (s.dead == 1) continue;
MAP[s.r][s.c] = p;
}
MAP[RUDOLF.r][RUDOLF.c] = RUDOLF_NUMBER;
}
int getNearSantaIndex()
{
int ret;
int minDistance = 0x7fff0000;
for (int r = N; r >= 1; r--)
{
for (int c = N; c >= 1; c--)
{
if (MAP[r][c] == 0 || MAP[r][c] == RUDOLF_NUMBER) continue;
int distance = getDistance(RUDOLF.r, RUDOLF.c, r, c);
if (distance < minDistance)
{
minDistance = distance;
ret = MAP[r][c];
}
}
}
return ret;
}
int getRudolfDirection(int santaIndex)
{
int direction = -1;
int minDistance = 0x7fff0000;
RC santa = SANTA[santaIndex];
for (int i = 0; i < 8; i++)
{
int nr, nc;
nr = RUDOLF.r + dr8[i];
nc = RUDOLF.c + dc8[i];
int distance = getDistance(nr, nc, santa.r, santa.c);
if (distance < minDistance)
{
minDistance = distance;
direction = i;
}
}
return direction;
}
void interaction(int santaIndex, int direction, int isRudolf)
{
RC startSanta = SANTA[santaIndex];
int candidate[30 + 5] = { 0 }; // 밀려날 산타들
int cnt = 0;
candidate[cnt++] = santaIndex;
int nr, nc;
nr = startSanta.r;
nc = startSanta.c;
while (1)
{
if (isRudolf == 1)
{
nr = nr + dr8[direction];
nc = nc + dc8[direction];
}
else
{
nr = nr + dr4[direction];
nc = nc + dc4[direction];
}
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (MAP[nr][nc] == 0) break;
candidate[cnt++] = MAP[nr][nc];
}
for (int i = 0; i < cnt; i++)
{
int index = candidate[i];
RC s = SANTA[index];
int snr, snc;
snr = s.r;
snc = s.c;
if (isRudolf == 1)
{
snr = snr + dr8[direction];
snc = snc + dc8[direction];
}
else
{
snr = snr + dr4[direction];
snc = snc + dc4[direction];
}
if (snr < 1 || snc < 1 || snr > N || snc > N)
{
SANTA[index].dead = 1;
continue;
}
SANTA[index].r = snr;
SANTA[index].c = snc;
}
}
void moveRudolf()
{
setMap();
int nearSantaIndex = getNearSantaIndex();
int rudolfDirection = getRudolfDirection(nearSantaIndex);
int nr, nc;
nr = RUDOLF.r + dr8[rudolfDirection];
nc = RUDOLF.c + dc8[rudolfDirection];
RUDOLF.r = nr;
RUDOLF.c = nc;
if (MAP[nr][nc] != 0) // 충돌 처리
{
int crashSantaIndex = MAP[nr][nc];
RC crashSanta = SANTA[crashSantaIndex];
int snr, snc;
snr = crashSanta.r + (dr8[rudolfDirection]) * C;
snc = crashSanta.c + (dc8[rudolfDirection]) * C;
// 외부로 나가는 경우
if (snr < 1 || snc < 1 || snr > N || snc > N) SANTA[crashSantaIndex].dead = 1;
else if (MAP[snr][snc] != 0) // 다른 산타가 있는 경우 (본인이 아닌 경우) 상호작용
{
int interSantaIndex = MAP[snr][snc];
interaction(interSantaIndex, rudolfDirection, 1);
}
SANTA[crashSantaIndex].r = snr;
SANTA[crashSantaIndex].c = snc;
SANTA[crashSantaIndex].stun = 2;
SANTA[crashSantaIndex].score += C;
}
}
void moveEachSanta(int santaIndex)
{
setMap();
RC santa = SANTA[santaIndex];
int currentDistance = getDistance(RUDOLF.r, RUDOLF.c, santa.r, santa.c);
int minDistance = 0x7fff0000;
int direction = -1;
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = santa.r + dr4[i];
nc = santa.c + dc4[i];
int nextDistance = getDistance(RUDOLF.r, RUDOLF.c, nr, nc);
if (currentDistance < nextDistance) continue; // 멀어지는 방향
if (MAP[nr][nc] == RUDOLF_NUMBER)
{
minDistance = 1;
direction = i;
break;
}
if (MAP[nr][nc] != 0) continue; // 다른 산타가 있는 경우
if (nextDistance < minDistance)
{
minDistance = nextDistance;
direction = i;
}
}
// 움직일 수 있는 공간이 없는 경우 종료
if (direction == -1) return;
SANTA[santaIndex].r = santa.r + dr4[direction];
SANTA[santaIndex].c = santa.c + dc4[direction];
// 움직인 공간에 루돌프가 있는 경우
if (MAP[SANTA[santaIndex].r][SANTA[santaIndex].c] == RUDOLF_NUMBER)
{
SANTA[santaIndex].stun = 1;
int changeDir[4] = { 2, 3, 0, 1 };
int snr, snc;
direction = changeDir[direction];
snr = SANTA[santaIndex].r + dr4[direction] * D;
snc = SANTA[santaIndex].c + dc4[direction] * D;
SANTA[santaIndex].score += D;
if (snr < 1 || snc < 1 || snr > N || snc > N)
{
SANTA[santaIndex].dead = 1;
return;
}
SANTA[santaIndex].r = snr;
SANTA[santaIndex].c = snc;
if (MAP[snr][snc] != 0) // 다른 산타가 있는 경우 (본인은 아닌 경우)
{
int interSantaIndex = MAP[snr][snc];
if (interSantaIndex != santaIndex) interaction(interSantaIndex, direction, 0);
}
}
}
void moveSanta()
{
for (int p = 1; p <= P; p++)
{
RC s = SANTA[p];
if (s.dead == 1) continue;
if (s.stun != 0)
{
SANTA[p].stun--;
continue;
}
moveEachSanta(p);
}
}
void scoreUp()
{
for (int p = 1; p <= P; p++)
{
if (SANTA[p].dead == 1) continue;
SANTA[p].score++;
}
}
int checkAllDeadSanta()
{
for (int p = 1; p <= P; p++)
if (SANTA[p].dead == 0) return 0;
return 1;
}
int main()
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
for (int m = 0; m < M; m++)
{
// 루돌프의 움직임 → 충돌 처리 → 상호작용
moveRudolf();
// 산타의 움직임 → 충돌 처리 → 상호작용
moveSanta();
// 게임 종료, 점수 계산
scoreUp();
if (checkAllDeadSanta() == 1) break;
}
for (int p = 1; p <= P; p++) printf("%d ", SANTA[p].score);
}
return 0;
}
'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
[코드트리] 고대 문명 유적 탐사 (삼성 SW 역량테스트 2024 상반기 오전 1번) (0) | 2024.08.11 |
---|---|
[코드트리] 코드트리 오마카세 (삼성 SW 역량테스트 2023 하반기 오후 2번, B형) (1) | 2024.08.11 |
[코드트리] 코드트리 메신저 (삼성 SW 역량테스트 2023 하반기 오전 2번, B형) (0) | 2024.08.08 |
[코드트리] 왕실의 기사 대결 (삼성 SW 역량테스트 2023 하반기 오전 1번) (0) | 2024.08.04 |
[코드트리] 코드트리 채점기 (삼성 SW 역량테스트 2023 상반기 오후 2번, B형 (0) | 2024.08.04 |
댓글