알고리즘/[ADV] 삼성 SW 역량 테스트 A형

[코드트리] 왕실의 기사 대결 (삼성 SW 역량테스트 2023 하반기 오전 1번)

피로물든딸기 2024. 8. 4. 21:23
반응형

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel

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

 

MAP은 함정과 벽만 기록한다.

tempMAP은 KNIGHT의 정보를 이용해 위치를 tempMAP에 표시하게 된다.

#define MAX (40 + 5)

int MAP[MAX][MAX]; // 함정과 벽만 기록
int tempMAP[MAX][MAX];

 

KNIGHT를 관리하기 위한 구조체를 선언한다.

originalHealth에 최초의 체력(k)을 저장한다.

기사의 생존 여부는 k <= 0으로 판단하고, 마지막에 계산할 damage는 originalHealth - k로 구한다.

typedef struct st
{
	int r;
	int c;
	int h;
	int w;
	int k;
	int originalHealth;
}KNIGHT_INFO;

KNIGHT_INFO KNIGHT[30 + 5];

 

위의 정보를 이용해 setMap에서 tempMAP에 기사의 위치를 적게 된다.

void setMap()
{
	for (int r = 1; r <= L; r++)
		for (int c = 1; c <= L; c++)
			tempMAP[r][c] = 0;

	for (int n = 1; n <= N; n++)
	{
		int r, c, h, w;

		if (KNIGHT[n].k <= 0) continue;

		r = KNIGHT[n].r;
		c = KNIGHT[n].c;
		h = KNIGHT[n].h;
		w = KNIGHT[n].w;

		for (int i = r; i < r + h; i++)
			for (int k = c; k < c + w; k++)
				tempMAP[i][k] = n;
	}
}

 

4방향 탐색을 위한 배열을 선언한다.

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

 

input은 다음과 같다.

KNIGHT의 번호 (1 ~ 30)을 구분하기 위해 함정(1)과 벽(2)을 각각 -1, -2로 변경하였다.

#define EMPTY (0)
#define TRAP (-1)
#define WALL (-2)

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

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

	for (int r = 1; r <= L; r++)
	{
		for (int c = 1; c <= L; c++)
		{
			scanf("%d", &MAP[r][c]);

			if (MAP[r][c] == 1) MAP[r][c] = -1;
			else if (MAP[r][c] == 2) MAP[r][c] = -2;
		}
	}

	for (int n = 1; n <= N; n++)
	{
		scanf("%d %d %d %d %d", &KNIGHT[n].r, &KNIGHT[n].c, &KNIGHT[n].h, &KNIGHT[n].w, &KNIGHT[n].k);

		// 최초 Energy 저장
		KNIGHT[n].originalHealth = KNIGHT[n].k;
	}
}

 

main에서 남은 input (i, q)를 입력 받아 모두 move한 후, 살아남은 기사의 데미지를 구한다.

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

		for (int q = 0; q < Q; q++)
		{
			int i, d;

			scanf("%d %d", &i, &d);

			move(i, d);
		}

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

	return 0;
}

기사 이동 및 대결 데미지

 

기사 이동은 다음과 같다.

 

체력(k)이 0 이하인 경우는 명령을 무시한다.

그리고 먼저 checkMove를 이용해 움직일 수 있는지 확인한다.

움직일 수 있다면, knightMove를 이용해 움직인다.

knightMove에서 움직인 기사는 함정이 있는 경우 체력이 감소된다.

하지만 명령을 받은 기사는 함정에 피해를 입지 않으므로, knightMove 이후 복구한다.

void move(int index, int direction)
{
	if (KNIGHT[index].k <= 0) return;

	int check = checkMove(index, direction);
	
	if (checkMove(index, direction) == 0) return;

	knightMove(index, direction);
	
	// 명령을 받은 기사는 TRAP에 의해 체력이 깎이지 않으므로, 복구
	KNIGHT_INFO knight = KNIGHT[index];
	for (int r = knight.r; r < knight.r + knight.h; r++)
		for (int c = knight.c; c < knight.c + knight.w; c++)
			if (MAP[r][c] == TRAP) KNIGHT[index].k++;
}

 

checkMove는 재귀 함수로 만든다.

주어진 기사의 번호(index)와 방향(direction)에 대해, 기사를 움직인다.

이때, (r, c)를 기준으로  (r + h - 1, c + w - 1) 까지 기사가 차지하고 있는 모든 배열을 움직인다. 

 

1) 배열을 움직이면서 벽을 만나면 움직일 수 없다.

2) 빈 배열이거나 자기 자신을 만나는 경우 (tempMAP[nr][nc] == index)는 움직일 수 있는 가능성이 있는 곳이다.

3) 그 외의 숫자는 다른 기사(nextKnightNumber)이므로, 만나게 된 기사를 움직일 수 있는지 확인해야 한다. 

ㄴ nextKnightNumber에 대해 checkMove를 다시 호출한다. (재귀)

ㄴ 한 번 nextKnightNumber로 checkMove를 한 경우, 다른 칸의 nextKnightNumber는 또 검사할 필요가 없다.

ㄴ 따라서, canMoveKnight에 mark 해둔다.

int checkMove(int index, int direction)
{
	setMap();

	KNIGHT_INFO knight = KNIGHT[index];	
	int canMoveKnight[30 + 5] = { 0 };

	for (int r = knight.r; r < knight.r + knight.h; r++)
	{
		for (int c = knight.c; c < knight.c + knight.w; c++)
		{
			int nr, nc;

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

			if (MAP[nr][nc] == WALL) return 0; // 벽을 만나는 경우, 이동 불가

			if (tempMAP[nr][nc] == EMPTY || tempMAP[nr][nc] == index) continue;

			int nextKnightNumber = tempMAP[nr][nc];
			
			if (canMoveKnight[nextKnightNumber] == 1) continue;
			
			canMoveKnight[nextKnightNumber] = 1;
			
			// 밀게 되는 기사가 이동 불가인 경우, 이동 불가
			if (checkMove(nextKnightNumber, direction) == 0) return 0;
		}
	}

	return 1;
}

 

knightMove도 위와 같은 원리로 구현한다.

움직일 수 있다는 것을 checkMove가 보장하기 때문에 연쇄적으로 움직이기만 하면 된다.

움직이고 나서, 함정이 있는 영역에 대해 체력을 감소하면 된다.

void knightMove(int index, int direction)
{
	setMap();

	KNIGHT_INFO knight = KNIGHT[index];
	int canMoveKnight[30 + 5] = { 0 };

	for (int r = knight.r; r < knight.r + knight.h; r++)
	{
		for (int c = knight.c; c < knight.c + knight.w; c++)
		{
			int nr, nc;

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

			if (tempMAP[nr][nc] == EMPTY || tempMAP[nr][nc] == index) continue;

			int nextKnightNumber = tempMAP[nr][nc];

			if (canMoveKnight[nextKnightNumber] == 1) continue;

			canMoveKnight[nextKnightNumber] = 1;

			knightMove(nextKnightNumber, direction);
		}
	}

	KNIGHT[index].r = KNIGHT[index].r + dr[direction];
	KNIGHT[index].c = KNIGHT[index].c + dc[direction];

	knight = KNIGHT[index]; // knight 갱신
	for (int r = knight.r; r < knight.r + knight.h; r++)
		for (int c = knight.c; c < knight.c + knight.w; c++)
			if (MAP[r][c] == TRAP) KNIGHT[index].k--;
}

 

생존한 기사의 데미지 합

 

생존 여부를 판단하여 최초의 체력(originalHealth)에 현재 체력을 뺀 값을 누적한다.

int getTotalDamage()
{
	int sum = 0;
	for (int i = 1; i <= N; i++)
		if (KNIGHT[i].k > 0) sum += (KNIGHT[i].originalHealth - KNIGHT[i].k);

	return sum;
}

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (40 + 5)

#define EMPTY (0)
#define TRAP (-1)
#define WALL (-2)

int T;
int L, N, Q;

int MAP[MAX][MAX]; // 함정과 벽만 기록
int tempMAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
	int h;
	int w;
	int k;
	int originalHealth;
}KNIGHT_INFO;

KNIGHT_INFO KNIGHT[30 + 5];

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

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

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

	for (int r = 1; r <= L; r++)
	{
		for (int c = 1; c <= L; c++)
		{
			scanf("%d", &MAP[r][c]);

			if (MAP[r][c] == 1) MAP[r][c] = -1;
			else if (MAP[r][c] == 2) MAP[r][c] = -2;
		}
	}

	for (int n = 1; n <= N; n++)
	{
		scanf("%d %d %d %d %d", &KNIGHT[n].r, &KNIGHT[n].c, &KNIGHT[n].h, &KNIGHT[n].w, &KNIGHT[n].k);

		// 최초 Energy 저장
		KNIGHT[n].originalHealth = KNIGHT[n].k;
	}
}

void printMap(int map[MAX][MAX])
{
	for (int n = 1; n <= N; n++)
		printf("%d] (%d, %d) %d, %d, : %d\n", n, KNIGHT[n].r, KNIGHT[n].c, KNIGHT[n].h, KNIGHT[n].w, KNIGHT[n].k);

	putchar('\n');

	for (int r = 1; r <= L; r++)
	{
		for (int c = 1; c <= L; c++)
			printf("%2d ", map[r][c]);
		putchar('\n');
	}

	printf("===========================================\n");
}

void setMap()
{
	for (int r = 1; r <= L; r++)
		for (int c = 1; c <= L; c++)
			tempMAP[r][c] = 0;

	for (int n = 1; n <= N; n++)
	{
		int r, c, h, w;

		if (KNIGHT[n].k <= 0) continue;

		r = KNIGHT[n].r;
		c = KNIGHT[n].c;
		h = KNIGHT[n].h;
		w = KNIGHT[n].w;

		for (int i = r; i < r + h; i++)
			for (int k = c; k < c + w; k++)
				tempMAP[i][k] = n;
	}
}

int checkMove(int index, int direction)
{
	setMap();

	KNIGHT_INFO knight = KNIGHT[index];	
	int canMoveKnight[30 + 5] = { 0 };

	for (int r = knight.r; r < knight.r + knight.h; r++)
	{
		for (int c = knight.c; c < knight.c + knight.w; c++)
		{
			int nr, nc;

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

			if (MAP[nr][nc] == WALL) return 0; // 벽을 만나는 경우, 이동 불가

			if (tempMAP[nr][nc] == EMPTY || tempMAP[nr][nc] == index) continue;

			int nextKnightNumber = tempMAP[nr][nc];
			
			if (canMoveKnight[nextKnightNumber] == 1) continue;
			
			canMoveKnight[nextKnightNumber] = 1;
			
			// 밀게 되는 기사가 이동 불가인 경우, 이동 불가
			if (checkMove(nextKnightNumber, direction) == 0) return 0;
		}
	}

	return 1;
}

void knightMove(int index, int direction)
{
	setMap();

	KNIGHT_INFO knight = KNIGHT[index];
	int canMoveKnight[30 + 5] = { 0 };

	for (int r = knight.r; r < knight.r + knight.h; r++)
	{
		for (int c = knight.c; c < knight.c + knight.w; c++)
		{
			int nr, nc;

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

			if (tempMAP[nr][nc] == EMPTY || tempMAP[nr][nc] == index) continue;

			int nextKnightNumber = tempMAP[nr][nc];

			if (canMoveKnight[nextKnightNumber] == 1) continue;

			canMoveKnight[nextKnightNumber] = 1;

			knightMove(nextKnightNumber, direction);
		}
	}

	KNIGHT[index].r = KNIGHT[index].r + dr[direction];
	KNIGHT[index].c = KNIGHT[index].c + dc[direction];

	knight = KNIGHT[index]; // knight 갱신
	for (int r = knight.r; r < knight.r + knight.h; r++)
		for (int c = knight.c; c < knight.c + knight.w; c++)
			if (MAP[r][c] == TRAP) KNIGHT[index].k--;
}

void move(int index, int direction)
{
	if (KNIGHT[index].k <= 0) return;

	int check = checkMove(index, direction);
	
	if (checkMove(index, direction) == 0) return;

	knightMove(index, direction);
	
	// 명령을 받은 기사는 TRAP에 의해 체력이 깎이지 않으므로, 복구
	KNIGHT_INFO knight = KNIGHT[index];
	for (int r = knight.r; r < knight.r + knight.h; r++)
		for (int c = knight.c; c < knight.c + knight.w; c++)
			if (MAP[r][c] == TRAP) KNIGHT[index].k++;
}

int getTotalDamage()
{
	int sum = 0;
	for (int i = 1; i <= N; i++)
		if (KNIGHT[i].k > 0) sum += (KNIGHT[i].originalHealth - KNIGHT[i].k);

	return sum;
}

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

		for (int q = 0; q < Q; q++)
		{
			int i, d;

			scanf("%d %d", &i, &d);

			move(i, d);
		}

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

	return 0;
}
반응형