[코드트리] 포탑 부수기 (삼성 SW 역량테스트 2023 상반기 오전 1번)

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

[코드트리] 포탑 부수기 (삼성 SW 역량테스트 2023 상반기 오전 1번)

피로물든딸기 2024. 7. 28. 01:38

삼성 A형 전체 링크

참고

- 코드트리 빵 (삼성 SW 역량테스트 2022 하반기 오후 1번)

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret

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

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

그리고 좌표별로 공격 시점을 기록하는 2차원 배열을 선언한다.

int attackTime[MAX][MAX];

우, 하, 좌, 상 우선순위로 움직일 수 있도록 dr, dc 배열을 선언한다.

// →, ↓, ←, ↑ 우/하/좌/상
int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};

input은 다음과 같다.

void input()
{
	scanf("%d %d %d", &N, &M, &K);

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

	// 시점 0에서 모두 공격
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			attackTime[r][c] = 0;
}

main은 input 이후, 시뮬레이션 결과를 출력하도록 한다.

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		printf("%d\n", simulate());
	}

	return 0;
}

시뮬레이션은 다음과 같이 진행된다.

0. 포탑 정비를 위해 공격 전 배열 저장

1. 공격자 선정

2. 공격자의 공격

2-1. target 탐색

2-2. target이 없는 경우 종료

2-3. target이 있는 경우 공격

3. 포탑 부서짐

4. 포탑 정비

5. 시뮬레이션 종료 후, 가장 큰 값을 return.

int simulate()
{
	for (int time = 1; time <= K; time++)
	{
		// 0. 현재 상태 저장
		int tempMAP[MAX][MAX] = { 0 };
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= M; c++)
				tempMAP[r][c] = MAP[r][c];

		// 1. 공격자 선정
		RC attacker = getWeakestTower();

		// 2. 공격자의 공격
		// 2-1. target 탐색
		RC target = getStrongestTower(attacker);

		// 2-2. target이 없는 경우 종료 = 부서지지 않은 포탑이 1개가 되는 경우
		if (target.r == 0 && target.c == 0) break;

		// 2-3. target이 있는 경우 공격
		MAP[attacker.r][attacker.c] += (M + N);
		attack(attacker, target, time);

		// 3. 포탑 부서짐
		setBrokenTower();

		// 4. 포탑 정비
		maintainTower(tempMAP);				
	}

	// 5. 가장 큰 값 탐색
	int maxPower = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (maxPower < MAP[r][c]) maxPower = MAP[r][c];

	return maxPower;
}

1. 공격자 선정

공격자 선정의 2번 조건을 위해 가장 최근 시간을 찾는 함수를 미리 만들어둔다.

숫자가 클수록 최근에 공격한 시간이다.

이때, 공격력이 가장 낮은 포탑(= minPower) 중 가장 최근 시간을 찾아야 된다.

int getRecentTime(int minPower)
{
	int recentTime = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (attackTime[r][c] > recentTime && MAP[r][c] == minPower) 
				recentTime = attackTime[r][c];

	return recentTime;
}

가장 약한 포탑을 찾는 함수를 만든다.

문제에서 제시한 조건을 한 번에 찾으려고 하면 복잡하기 때문에, 각 조건마다 후보자를 선정하였다.

후보가 1명인 경우 return하면 된다.

RC getWeakestTower()
{
	RC candidate[MAX * MAX] = { 0 };
	int cidx = 0;

	int power = 0;
	int minPower = 0x7fff0000;	
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (MAP[r][c] == 0) continue;
			if (MAP[r][c] < minPower) minPower = MAP[r][c];
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{			
			if (MAP[r][c] == minPower)
			{
				candidate[cidx].r = r;
				candidate[cidx++].c = c;
			}
		}
	}

	// 가장 약한 포탑이 1개인 경우
	if (cidx == 1) return candidate[0];

	int recentTime = getRecentTime(minPower);

	int length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if (attackTime[candidate[i].r][candidate[i].c] == recentTime)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 행과 열의 합이 가장 큰 포탑 구하기
	int maxRC = 0;
	for (int i = 0; i < cidx; i++)
		if (maxRC < (candidate[i].r + candidate[i].c))
			maxRC = (candidate[i].r + candidate[i].c);		

	length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if ((candidate[i].r + candidate[i].c) == maxRC)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 열 값이 가장 큰 포탑 구하기
	RC ret = { 0 };
	int maxC = 0;
	for (int i = 0; i < cidx; i++)
	{
		if (maxC < candidate[i].c)
		{
			maxC = candidate[i].c;
			ret = candidate[i];
		}
	}
	
	return ret;
}

2. 공격자의 공격

2-1. target 탐색

공격자와 반대로 공격한지 가장 오래된 시간을 찾는 함수를 만든다.

int getLastTime(int maxPower)
{
	int lastTime = 0x7fff0000;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (attackTime[r][c] < lastTime && MAP[r][c] == maxPower) 
				lastTime = attackTime[r][c];

	return lastTime;
}

가장 강한 포탑을 찾아야 한다.

이때, 공격자를 제외해야 하므로 attacker를 제외하고 탐색해야 한다.

attacker만 남는 경우 (0, 0)을 return하게 된다.

RC getStrongestTower(RC attacker)
{
	RC candidate[MAX * MAX] = { 0 };
	int cidx = 0;

	int power = 0;
	int maxPower = -1;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			// 공격자를 제외한 가장 강한 포탑
			if (attacker.r == r && attacker.c == c) continue;
			if (MAP[r][c] == 0) continue;
			if (MAP[r][c] > maxPower) maxPower = MAP[r][c];
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (attacker.r == r && attacker.c == c) continue;

			if (MAP[r][c] == maxPower)
			{
				candidate[cidx].r = r;
				candidate[cidx++].c = c;
			}
		}
	}

	// 가장 강한 포탑이 1개인 경우
	if (cidx == 1) return candidate[0];

	int lastTime = getLastTime(maxPower);

	int length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if (attackTime[candidate[i].r][candidate[i].c] == lastTime)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 행과 열의 합이 가장 작은 포탑 구하기
	int minRC = 0x7fff0000;
	for (int i = 0; i < cidx; i++)
		if (minRC > (candidate[i].r + candidate[i].c))
			minRC = (candidate[i].r + candidate[i].c);

	length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if ((candidate[i].r + candidate[i].c) == minRC)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 열 값이 가장 작은 포탑 구하기
	RC ret = { 0 };
	int minC = 0x7fff0000;
	for (int i = 0; i < cidx; i++)
	{
		if (minC > candidate[i].c)
		{
			minC = candidate[i].c;
			ret = candidate[i];
		}
	}

	return ret;
}

2-2. target이 없는 경우 종료

RC ret = {0} 이 아무 값을 할당받지 못한 경우는 부서지지 않은 포탑이 1개가 되는 경우다.

따라서 시뮬레이션을 종료한다.

if (target.r == 0 && target.c == 0) break;

2-3. target이 있는 경우 공격

공격자의 공격력을 (M + N)만큼 증가시키고 attack 함수를 실행한다.

	MAP[attacker.r][attacker.c] += (M + N);
	attack(attacker, target, time);

attack은 다음과 같다.

- attackTime에 현재 공격한 시간을 기록한다.

- laser를 실행한다. (laser가 0을 return하는 경우는 포탄을 던져야 한다.)

- target 주변 8방향에 포탄을 던진다.

8방향 포탄을 던지는 경우, attacker는 제외해야 한다.

void attack(RC attacker, RC target, int time)
{	
	attackTime[attacker.r][attacker.c] = time;

	if(laser(attacker, target) == 1) return;

	/* ←, ↖, ↑, ↗, →, ↘, ↓, ↙  */
	int dr8[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
	int dc8[] = { -1, -1, 0, 1, 1, 1, 0, -1 };

	int sr = attacker.r;
	int sc = attacker.c;
	int er = target.r;
	int ec = target.c;

	int power = MAP[sr][sc];

	MAP[er][ec] -= power;
	for (int i = 0; i < 8; i++)
	{
		int nr = ((er + dr8[i] + N) - 1) % N + 1;
		int nc = ((ec + dc8[i] + M) - 1) % M + 1;

		if (MAP[nr][nc] == 0) continue;
		if (nr == sr && nc == sc) continue; // 공격자는 영향을 받지 않음.

		MAP[nr][nc] -= (power / 2);
	}
}

이 문제는 좌표가 넘어가는 경우 반대 방향의 좌표에서 시작하기 때문에 나머지 연산을 이용해 좌표를 갱신하였다.

	int nr = ((er + dr8[i] + N) - 1) % N + 1;
	int nc = ((ec + dc8[i] + M) - 1) % M + 1;

laser는 다음과 같다.

코드트리 빵에서 사용한 방법으로 before 배열에 경로를 기억한다.

2차원 BFS 탐색으로 start (공격자) → end (공격 대상)에 도달할 수 있는 경우,

before 배열로 경로를 추적하면서 MAP을 갱신한다.

int laser(RC start, RC end)
{
	RC queue[MAX * MAX] = { 0 };
	int rp, wp;

	int visit[MAX][MAX] = { 0 };
	RC before[MAX][MAX] = { 0 }; // 코드트리 빵

	rp = wp = 0;

	int sr = start.r;
	int sc = start.c;
	int er = end.r;
	int ec = end.c;

	queue[wp].r = sr;
	queue[wp++].c = sc;
	
	before[sr][sc].r = -1;
	before[sr][sc].c = -1;

	visit[sr][sc] = 1;

	while (rp < wp)
	{
		RC out = queue[rp++];

		if (out.r == end.r && out.c == end.c)
		{
			int power = MAP[sr][sc];
			
			int tr = out.r;
			int tc = out.c;

			MAP[tr][tc] -= power;

			// 이전 좌표를 찾으면서 처리			
			while (1)
			{
				// 이전 좌표
				int br = before[tr][tc].r;
				int bc = before[tr][tc].c;
	 
				if (br == sr && bc == sc) break;

				MAP[br][bc] -= (power / 2);

				tr = br;
				tc = bc;
			}

			return 1;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr = ((out.r + dr[i] + N) - 1) % N + 1;
			int nc = ((out.c + dc[i] + M) - 1) % M + 1;

			if (MAP[nr][nc] != 0 && visit[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				before[nr][nc].r = out.r; // 이전 좌표 기억
				before[nr][nc].c = out.c;

				visit[nr][nc] = 1;
			}
		}
	}
	
	return 0;
}

8방향 포탄과 마찬가지로, 좌표를 넘어서는 경우 반대편으로 나오기 때문에 나머지 연산으로 처리하였다.

	int nr = ((out.r + dr[i] + N) - 1) % N + 1;
	int nc = ((out.c + dc[i] + M) - 1) % M + 1;

3. 포탑 부서짐

0보다 작은 값을 0으로 만든다.

void setBrokenTower()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (MAP[r][c] < 0) MAP[r][c] = 0;	
}

4. 포탑 정비

공격을 하기 전 저장해둔 좌표와 비교해서 변화가 있는 경우 값을 1 증가한다.

void maintainTower(int tempMAP[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (tempMAP[r][c] == 0) continue;
			if (tempMAP[r][c] != MAP[r][c]) continue;
			
			MAP[r][c]++;
		}
	}
}

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (10 + 5)

int T;
int N, M, K;

int MAP[MAX][MAX];

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

int attackTime[MAX][MAX];

// →, ↓, ←, ↑ 우/하/좌/상
int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};

void input()
{
	scanf("%d %d %d", &N, &M, &K);

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

	// 시점 0에서 모두 공격
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			attackTime[r][c] = 0;
}

void printMap()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
			
	putchar('\n');
}

int getRecentTime(int minPower)
{
	int recentTime = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (attackTime[r][c] > recentTime && MAP[r][c] == minPower) 
				recentTime = attackTime[r][c];

	return recentTime;
}

int getLastTime(int maxPower)
{
	int lastTime = 0x7fff0000;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (attackTime[r][c] < lastTime && MAP[r][c] == maxPower) 
				lastTime = attackTime[r][c];

	return lastTime;
}

RC getWeakestTower()
{
	RC candidate[MAX * MAX] = { 0 };
	int cidx = 0;

	int power = 0;
	int minPower = 0x7fff0000;	
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (MAP[r][c] == 0) continue;
			if (MAP[r][c] < minPower) minPower = MAP[r][c];
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{			
			if (MAP[r][c] == minPower)
			{
				candidate[cidx].r = r;
				candidate[cidx++].c = c;
			}
		}
	}

	// 가장 약한 포탑이 1개인 경우
	if (cidx == 1) return candidate[0];

	int recentTime = getRecentTime(minPower);

	int length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if (attackTime[candidate[i].r][candidate[i].c] == recentTime)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 행과 열의 합이 가장 큰 포탑 구하기
	int maxRC = 0;
	for (int i = 0; i < cidx; i++)
		if (maxRC < (candidate[i].r + candidate[i].c))
			maxRC = (candidate[i].r + candidate[i].c);		

	length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if ((candidate[i].r + candidate[i].c) == maxRC)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 열 값이 가장 큰 포탑 구하기
	RC ret = { 0 };
	int maxC = 0;
	for (int i = 0; i < cidx; i++)
	{
		if (maxC < candidate[i].c)
		{
			maxC = candidate[i].c;
			ret = candidate[i];
		}
	}
	
	return ret;
}

RC getStrongestTower(RC attacker)
{
	RC candidate[MAX * MAX] = { 0 };
	int cidx = 0;

	int power = 0;
	int maxPower = -1;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			// 공격자를 제외한 가장 강한 포탑
			if (attacker.r == r && attacker.c == c) continue;
			if (MAP[r][c] == 0) continue;
			if (MAP[r][c] > maxPower) maxPower = MAP[r][c];
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (attacker.r == r && attacker.c == c) continue;

			if (MAP[r][c] == maxPower)
			{
				candidate[cidx].r = r;
				candidate[cidx++].c = c;
			}
		}
	}

	// 가장 강한 포탑이 1개인 경우
	if (cidx == 1) return candidate[0];

	int lastTime = getLastTime(maxPower);

	int length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if (attackTime[candidate[i].r][candidate[i].c] == lastTime)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 행과 열의 합이 가장 작은 포탑 구하기
	int minRC = 0x7fff0000;
	for (int i = 0; i < cidx; i++)
		if (minRC > (candidate[i].r + candidate[i].c))
			minRC = (candidate[i].r + candidate[i].c);

	length = cidx;
	cidx = 0;
	for (int i = 0; i < length; i++)
		if ((candidate[i].r + candidate[i].c) == minRC)
			candidate[cidx++] = candidate[i];

	if (cidx == 1) return candidate[0];

	// 열 값이 가장 작은 포탑 구하기
	RC ret = { 0 };
	int minC = 0x7fff0000;
	for (int i = 0; i < cidx; i++)
	{
		if (minC > candidate[i].c)
		{
			minC = candidate[i].c;
			ret = candidate[i];
		}
	}

	return ret;
}

int laser(RC start, RC end)
{
	RC queue[MAX * MAX] = { 0 };
	int rp, wp;

	int visit[MAX][MAX] = { 0 };
	RC before[MAX][MAX] = { 0 }; // 코드트리 빵

	rp = wp = 0;

	int sr = start.r;
	int sc = start.c;
	int er = end.r;
	int ec = end.c;

	queue[wp].r = sr;
	queue[wp++].c = sc;
	
	before[sr][sc].r = -1;
	before[sr][sc].c = -1;

	visit[sr][sc] = 1;

	while (rp < wp)
	{
		RC out = queue[rp++];

		if (out.r == end.r && out.c == end.c)
		{
			int power = MAP[sr][sc];
			
			int tr = out.r;
			int tc = out.c;

			MAP[tr][tc] -= power;

			// 이전 좌표를 찾으면서 처리			
			while (1)
			{
				// 이전 좌표
				int br = before[tr][tc].r;
				int bc = before[tr][tc].c;
	 
				if (br == sr && bc == sc) break;

				MAP[br][bc] -= (power / 2);

				tr = br;
				tc = bc;
			}

			return 1;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr = ((out.r + dr[i] + N) - 1) % N + 1;
			int nc = ((out.c + dc[i] + M) - 1) % M + 1;

			if (MAP[nr][nc] != 0 && visit[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				before[nr][nc].r = out.r; // 이전 좌표 기억
				before[nr][nc].c = out.c;

				visit[nr][nc] = 1;
			}
		}
	}
	
	return 0;
}

void attack(RC attacker, RC target, int time)
{	
	attackTime[attacker.r][attacker.c] = time;

	if(laser(attacker, target) == 1) return;

	/* ←, ↖, ↑, ↗, →, ↘, ↓, ↙  */
	int dr8[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
	int dc8[] = { -1, -1, 0, 1, 1, 1, 0, -1 };

	int sr = attacker.r;
	int sc = attacker.c;
	int er = target.r;
	int ec = target.c;

	int power = MAP[sr][sc];

	MAP[er][ec] -= power;
	for (int i = 0; i < 8; i++)
	{
		int nr = ((er + dr8[i] + N) - 1) % N + 1;
		int nc = ((ec + dc8[i] + M) - 1) % M + 1;

		if (MAP[nr][nc] == 0) continue;
		if (nr == sr && nc == sc) continue; // 공격자는 영향을 받지 않음.

		MAP[nr][nc] -= (power / 2);
	}
}

void setBrokenTower()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (MAP[r][c] < 0) MAP[r][c] = 0;	
}

void maintainTower(int tempMAP[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (tempMAP[r][c] == 0) continue;
			if (tempMAP[r][c] != MAP[r][c]) continue;
			
			MAP[r][c]++;
		}
	}
}

int simulate()
{
	for (int time = 1; time <= K; time++)
	{
		// 0. 현재 상태 저장
		int tempMAP[MAX][MAX] = { 0 };
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= M; c++)
				tempMAP[r][c] = MAP[r][c];

		// 1. 공격자 선정
		RC attacker = getWeakestTower();

		// 2. 공격자의 공격
		// 2-1. target 탐색
		RC target = getStrongestTower(attacker);

		// 2-2. target이 없는 경우 종료 = 부서지지 않은 포탑이 1개가 되는 경우
		if (target.r == 0 && target.c == 0) break;

		// 2-3. target이 있는 경우 공격
		MAP[attacker.r][attacker.c] += (M + N);
		attack(attacker, target, time);

		// 3. 포탑 부서짐
		setBrokenTower();

		// 4. 포탑 정비
		maintainTower(tempMAP);				
	}

	// 5. 가장 큰 값 탐색
	int maxPower = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (maxPower < MAP[r][c]) maxPower = MAP[r][c];

	return maxPower;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		printf("%d\n", simulate());
	}

	return 0;
}