By 정우석 in Problem Solving —

포탑 부수기 [2023-상반기 오전 1번 문제]

문제 링크

삼성 코딩테스트 기출 문제: 포탑 부수기 - 코드트리
주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.
코드트리

문제 설명

N*M 격자가 있고, 모든 위치에는 포탑이 존재함. 각 포탑에는 공격력이 존재하며, 공격력이 0 이하가 되면, 부셔진 것으로 간주함. 최초에 0이 있을 수 있음.

  1. 공격자 선정부서지지 않은 포탑 중 가장 약한 포탑을 선정 (공격력 가장 낮은 → 가장 최근에 공격한 포탑 → 행+열 합 큰 → 열 큰) 공격자의 공격력이 N+M만큼 증가
  2. 공격자의 공격공격자를 제외한 가장 강한 포탑 선정. (공격력 가장 높은 → 공격한지 가장 오래된 포탑 → 행+열 합 작은 → 열 작은)
    1. 레이저 공격최단거리 → 우하좌상의 우선순위로 먼저 움직인 경로. 격자 벗어난다면 반대편으로 이동 가능. 경로에 있는 포탑들은 공격자/2의 데미지, 타겟은 공격자만큼 데미지 받음.
    2. 포탄 공격레이저 공격이 안된다면 타겟 + 주위 8개의 포탑에게 공격. 격자를 벗어난다면 반대편 격자에 미치게 됨. 타겟은 공격자만큼, 그 나머지는 공격자/2의 데미지
  3. 포탑 부셔짐공격을 받아 공격력이 0이 된 포탑은 부셔짐
  4. 포탑 정비부셔지지 않은 포탑 중 공격과 무관한 포탑들은 공격력이 1씩 올라감

해결 방법

  1. 공격자 선정

공격자를 우선순위대로 선정 후, 데미지를 늘려줌.

bool not_chosen = true;
for (int i = 0;i < n;i++) {
	for (int j = 0;j < m;j++) {
		// 부셔진 애
		if (arr[i][j].a == 0) continue;
		// 첫 번째
		if (not_chosen) {
			ax = i, ay = j;
			not_chosen = false;
			continue;
		}
		if (arr[i][j].a < arr[ax][ay].a) { // 1. 낮은 공격력
			ax = i, ay = j;
		}
		else if (arr[i][j].a == arr[ax][ay].a && arr[i][j].attacked > arr[ax][ay].attacked) {
			ax = i, ay = j;
		}
		else if (arr[i][j].a == arr[ax][ay].a && arr[i][j].attacked == arr[ax][ay].attacked && ax + ay < i+j) { // 행 열 높은 순
			ax = i, ay = j;
		}
		else if (arr[i][j].a == arr[ax][ay].a && arr[i][j].attacked == arr[ax][ay].attacked && ax + ay == i + j && ay < j) {
			ax = i, ay = j;
		}
	}
}

arr[ax][ay].attacked = t;
arr[ax][ay].a += (n + m);
  1. 피공격자 선정
not_chosen = true;
for (int i = 0;i < n;i++) {
	for (int j = 0;j < m;j++) {
		if (arr[i][j].a == 0) continue;
		if (i == ax && j == ay) continue;
		if (not_chosen) {
			tx = i, ty = j;
			not_chosen = false;
			continue;
		}		
		if (arr[i][j].a > arr[tx][ty].a) {
			tx = i, ty = j;
		}
		else if (arr[i][j].a == arr[tx][ty].a && arr[i][j].attacked < arr[tx][ty].attacked) { // 가장 늦게 공격한 순
			tx = i, ty = j;
		}
		else if (arr[i][j].a == arr[tx][ty].a && arr[i][j].attacked == arr[tx][ty].attacked && tx + ty > i + j) { // 행 열 높은 순
			tx = i, ty = j;
		}
		else if (arr[i][j].a == arr[tx][ty].a && arr[i][j].attacked == arr[tx][ty].attacked && tx + ty == i + j && ty > j) { // 행 열 높은 순
			tx = i, ty = j;
		}
	}
}
  1. 레이저 공격
bool laser_attack() {
	int dx[4] = { 0,1,0,-1 };
	int dy[4] = { 1,0,-1,0 };

	// 메모리 초기화
	memset(visited, 0, sizeof(visited));
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			parent[i][j].x = -1, parent[i][j].y = -1;
		}
	}

	// 시작 push
	queue<pair<int, int>> que;
	que.push({ ax,ay });
	visited[ax][ay] = 1;

	int cx, cy, nx, ny;
	while (!que.empty()) {
		tie(cx, cy) = que.front();
		que.pop();

		for (int i = 0;i < 4;i++) {
			nx = cx + dx[i], ny = cy + dy[i];

			// 격자를 넘었을 때
			if (nx < 0) nx = n - 1; if (ny < 0) ny = m - 1;
			if (nx >= n) nx = 0; if (ny >= m) ny = 0;

			if (visited[nx][ny]) continue;
			if (arr[nx][ny].a == 0) continue;

			visited[nx][ny] = 1;
			parent[nx][ny].x = cx, parent[nx][ny].y = cy;
			que.push({ nx,ny });
		}
	}
	if (!visited[tx][ty]) return false;
	memset(visited, 0, sizeof(visited));
	cx = tx, cy = ty;
	int ctx, cty;
	while (!(cx == ax && cy == ay)) {
		if (cx == tx && cy == ty) arr[cx][cy].a -= arr[ax][ay].a;
		else arr[cx][cy].a -= (arr[ax][ay].a / 2);
		visited[cx][cy] = 1;
		if (arr[cx][cy].a < 0) arr[cx][cy].a = 0;
		ctx = cx, cty = cy;
		cx = parent[ctx][cty].x;
		cy = parent[ctx][cty].y;
	}

	visited[ax][ay] = 1;

	return true;
}
  1. 포탑 공격
void bomb_attack() {
	memset(visited, 0, sizeof(visited));
	int dx[8] = { -1,-1,-1,0,0,1,1,1 };
	int dy[8] = { -1,0,1,-1,1,-1,0,1 };

	int nx, ny;
	for (int i = 0;i < 8;i++) {
		nx = tx + dx[i], ny = ty + dy[i];
		if (nx < 0) nx = n - 1; if (ny < 0) ny = m - 1;
		if (nx >= n) nx = 0; if (ny >= m) ny = 0;
		if (nx == ax && ny == ay) continue;
		if (arr[nx][ny].a == 0) continue;
		visited[nx][ny] = 1;
		arr[nx][ny].a -= (arr[ax][ay].a / 2);
		if (arr[nx][ny].a < 0) arr[nx][ny].a = 0;
	}
	arr[tx][ty].a -= arr[ax][ay].a;
	if (arr[tx][ty].a < 0) arr[tx][ty].a = 0;

	visited[ax][ay] = 1, visited[tx][ty] = 1;
}
  1. 포탑 정비
for (int i = 0;i < n;i++) {
	for (int j = 0;j < m;j++) {
		if (!visited[i][j] && arr[i][j].a > 0) {
			arr[i][j].a += 1;
		}
	}
}

전체 코드

#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
#include <cstdio>
using namespace std;

typedef struct {
	int a;
	int attacked;
}_tower;

typedef struct {
	int x, y;
}_loc;

int n, m, k;
_tower arr[15][15]; // 최대 10

void input() {
	cin >> n >> m >> k;

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> arr[i][j].a;
			arr[i][j].attacked = 0;
		}
	}
}

int visited[15][15];
_loc parent[15][15];
int ax, ay, tx, ty;

bool laser_attack() {
	int dx[4] = { 0,1,0,-1 };
	int dy[4] = { 1,0,-1,0 };

	// 메모리 초기화
	memset(visited, 0, sizeof(visited));
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			parent[i][j].x = -1, parent[i][j].y = -1;
		}
	}

	// 시작 push
	queue<pair<int, int>> que;
	que.push({ ax,ay });
	visited[ax][ay] = 1;

	int cx, cy, nx, ny;
	while (!que.empty()) {
		tie(cx, cy) = que.front();
		que.pop();

		for (int i = 0;i < 4;i++) {
			nx = cx + dx[i], ny = cy + dy[i];

			// 격자를 넘었을 때
			if (nx < 0) nx = n - 1; if (ny < 0) ny = m - 1;
			if (nx >= n) nx = 0; if (ny >= m) ny = 0;

			if (visited[nx][ny]) continue;
			if (arr[nx][ny].a == 0) continue;

			visited[nx][ny] = 1;
			parent[nx][ny].x = cx, parent[nx][ny].y = cy;
			que.push({ nx,ny });
		}
	}
	if (!visited[tx][ty]) return false;
	memset(visited, 0, sizeof(visited));
	cx = tx, cy = ty;
	int ctx, cty;
	while (!(cx == ax && cy == ay)) {
		if (cx == tx && cy == ty) arr[cx][cy].a -= arr[ax][ay].a;
		else arr[cx][cy].a -= (arr[ax][ay].a / 2);
		visited[cx][cy] = 1;
		if (arr[cx][cy].a < 0) arr[cx][cy].a = 0;
		ctx = cx, cty = cy;
		cx = parent[ctx][cty].x;
		cy = parent[ctx][cty].y;
	}

	visited[ax][ay] = 1;

	return true;
}

void bomb_attack() {
	memset(visited, 0, sizeof(visited));
	int dx[8] = { -1,-1,-1,0,0,1,1,1 };
	int dy[8] = { -1,0,1,-1,1,-1,0,1 };

	int nx, ny;
	for (int i = 0;i < 8;i++) {
		nx = tx + dx[i], ny = ty + dy[i];
		if (nx < 0) nx = n - 1; if (ny < 0) ny = m - 1;
		if (nx >= n) nx = 0; if (ny >= m) ny = 0;
		if (nx == ax && ny == ay) continue;
		if (arr[nx][ny].a == 0) continue;
		visited[nx][ny] = 1;
		arr[nx][ny].a -= (arr[ax][ay].a / 2);
		if (arr[nx][ny].a < 0) arr[nx][ny].a = 0;
	}
	arr[tx][ty].a -= arr[ax][ay].a;
	if (arr[tx][ty].a < 0) arr[tx][ty].a = 0;

	visited[ax][ay] = 1, visited[tx][ty] = 1;
}

void solve(int t) {
	// 1. 공격자 선정
	bool not_chosen = true;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			// 부셔진 애
			if (arr[i][j].a == 0) continue;
			// 첫 번째
			if (not_chosen) {
				ax = i, ay = j;
				not_chosen = false;
				continue;
			}
			if (arr[i][j].a < arr[ax][ay].a) { // 1. 낮은 공격력
				ax = i, ay = j;
			}
			else if (arr[i][j].a == arr[ax][ay].a && arr[i][j].attacked > arr[ax][ay].attacked) {
				ax = i, ay = j;
			}
			else if (arr[i][j].a == arr[ax][ay].a && arr[i][j].attacked == arr[ax][ay].attacked && ax + ay < i+j) { // 행 열 높은 순
				ax = i, ay = j;
			}
			else if (arr[i][j].a == arr[ax][ay].a && arr[i][j].attacked == arr[ax][ay].attacked && ax + ay == i + j && ay < j) {
				ax = i, ay = j;
			}
		}
	}

	// 2. 타겟 선정
	not_chosen = true;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (arr[i][j].a == 0) continue;
			if (i == ax && j == ay) continue;
			if (not_chosen) {
				tx = i, ty = j;
				not_chosen = false;
				continue;
			}		
			if (arr[i][j].a > arr[tx][ty].a) {
				tx = i, ty = j;
			}
			else if (arr[i][j].a == arr[tx][ty].a && arr[i][j].attacked < arr[tx][ty].attacked) { // 가장 늦게 공격한 순
				tx = i, ty = j;
			}
			else if (arr[i][j].a == arr[tx][ty].a && arr[i][j].attacked == arr[tx][ty].attacked && tx + ty > i + j) { // 행 열 높은 순
				tx = i, ty = j;
			}
			else if (arr[i][j].a == arr[tx][ty].a && arr[i][j].attacked == arr[tx][ty].attacked && tx + ty == i + j && ty > j) { // 행 열 높은 순
				tx = i, ty = j;
			}
		}
	}

	if (not_chosen) {
		return;
	}
	arr[ax][ay].attacked = t;
	arr[ax][ay].a += (n + m);

	// 3. 레이저 공격
	if (!laser_attack()) {
		bomb_attack();
	}

	// 4. 무관한 애들은 +1
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (!visited[i][j] && arr[i][j].a > 0) {
				arr[i][j].a += 1;
			}
		}
	}

	return;
}

void print_map() {
	printf("===== print_map =====\\n");
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			printf("%5d ", arr[i][j].a);
		}
		printf("\\n");
	}
	printf("\\n");
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

//	freopen("sample_input.txt", "r", stdin);
	input();
	for (int i = 0;i < k;i++) {
		solve(i+1);
	}

	int result = 0;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (arr[i][j].a != 0) {
				if (arr[i][j].a > result) {
					result = arr[i][j].a;
				}
			}
		}
	}

	cout << result;
}
Previous

왕실의 기사 대결 [2023-하반기 오후 1번 문제]

 Next

메이즈 러너 [2023-상반기 오후 1번 문제]

You might also like...