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;
}
'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
[코드트리] 메이즈 러너 (삼성 SW 역량테스트 2023 상반기 오후 1번) (0) | 2024.07.31 |
---|---|
[코드트리] 토끼와 경주 (삼성 SW 역량테스트 2023 상반기 오전 2번, B형) (0) | 2024.07.28 |
[코드트리] 산타의 선물 공장 2 (삼성 SW 역량테스트 2022 하반기 오후 2번, B형) (0) | 2024.07.27 |
[코드트리] 코드트리 빵 (삼성 SW 역량테스트 2022 하반기 오후 1번) (0) | 2024.07.19 |
[코드트리] 산타의 선물 공장 (삼성 SW 역량테스트 2022 하반기 오전 2번, B형) (0) | 2024.07.13 |
댓글