[코드트리] 루돌프의 반란 (삼성 SW 역량테스트 2023 하반기 오후 1번)

피로물든딸기 2024. 8. 8. 00:42

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;
}