📖 APS/CodeTree
[APS][CodeTree] 삼성 SW 역량 테스트 2023년 상반기 오전 1번 문제 - 포탑 부수기
청월누리
2025. 4. 12. 00:18
삼성 코딩테스트 기출 문제 설명: 포탑 부수기 | 코드트리
삼성 코딩테스트 기출 문제 설명: 포탑 부수기 | 코드트리
삼성전자 코딩테스트 기출 문제 포탑 부수기의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.
www.codetree.ai
문제
문제가 너무 길어서 생략... 위 링크에서 확인 가능합니다.
입력
출력
풀이
- BFS(너비 우선 탐색)를 이용한 최단 거리 + 시뮬레이션(구현) 문제
- 주어진 조건을 따져가며, 함수를 이용하여 단계적으로 구현하는 것이 실수를 줄이는 법
- 초기화(
void init()) : 어떻게 초기화를 할 것인가? 포탑의 정보는 어떻게 받아올 것인가? 고민 - 공격자 선정(
Tower findAttacker()) : 문제에서 주어진 조건에 따라 공격 포탑 선택 - 타겟 선정 (
Tower findTarget()) : 문제에서 주어진 조건에 따라 공격 타겟이 될 포탑 선택 - 레이저 공격 (
void laser(int y, int x)) : 조건에 따라 최단 경로 탐색 (BFS 알고리즘) - 포탑 공격 : 레이저 공격이 불가능할 경우 수행
- 포탑 정비 : 한 턴이 종료되면 (공격이 모두 마무리되면), 조건에 따라 포탑 정비 수행
- 초기화(
코드
세부 코드 설명
포탑 정보 입력
...
struct Tower {
int id; // 임의의 포탑 ID
int row; // 위치좌표
int col;
int atk; // 공격력
int last_turn = 0; // 최근 공격한 turn
};
int N, M, K;
int remain_tower = 0;
vector<vector<Tower>> map; // 포탑 지도
vector<bool> isdestroy; // 파괴 여부 저장 (ID 기반)
vector<vector<int>> visited; // 최단 거리 (방문 여부)
vector<Tower> path; // 방문 경로 (ID 기반)
vector<bool> isAttack; // 공격 관여 여부
...struct Tower: 구조체를 이용하여 필요한 포탑 정보 준비id: 포탑을 구분할 ID (0 ~ $ N * M - 1 $ 번으로 설정)row,col: 포탑이 위치한 세로(row), 가로(col) 위치atk: 포탑의 공격력 (공격력이자 동시에 체력)last_turn: 포탑이 마지막으로 공격한 턴
N,M,K: 기본적인 맵 및 게임 정보 (각각 세로, 가로, 최대 턴)remain_tower: 살아있는 포탑의 개수 (모든 턴이 끝나기 전에 종료 체크를 위함)vector<vector<Tower>> map: 포탑 배치 지도 + 각 포탑 정보(구조체)를 담을 배열vector<bool> isdestroy: 포탑 파괴 여부 (ID 기반으로 동작하는 DAT, 탐색 시간 줄이기 위함)vector<vector<int>> visited: BFS 탐색을 위한 방문 체크 배열 (방문 체크 겸 최단 거리 탐색)vector<Tower> path: BFS 탐색 경로 저장용vector<bool> isAttack: 공격 관여 여부 (ID 기반 동작 DAT, 공격자, 타겟, 공격 맞은 다른 포탑들)
초기화 함수
...
void init() {
cin >> N >> M >> K;
map.resize(N, vector<Tower>(M));
isdestroy.resize(N * M, true);
int id = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Tower temp = {id, i, j, 0};
cin >> temp.atk;
if (temp.atk != 0) {
isdestroy[temp.id] = false;
remain_tower++;
}
map[i][j] = temp;
id++;
}
}
return;
}
...- 처음 입력을 받기 위한 함수
- 포탑 배치 정보 + 포탑 정보를 모두 저장하는 기능 수행
공격자 선정 함수
...
Tower findAttacker() {
Tower choice = {0, 0, 0, INT_MAX, 0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Tower now = map[i][j];
if (now.atk == 0) continue;
if (choice.atk >= now.atk) {
if (choice.atk > now.atk)
choice = now;
else {
if (choice.last_turn < now.last_turn)
choice = now;
else if (choice.last_turn == now.last_turn) {
if (choice.row + choice.col < now.row + now.col)
choice = now;
else if (choice.row + choice.col == now.row + now.col) {
if (choice.col < now.col) choice = now;
}
}
}
}
}
}
return choice;
}
...- 문제에서 주어진 조건에 따라 완전 탐색으로 공격 포탑을 찾는 함수
- 찾은 공격 포탑 정보는
Tower구조체로 반환
타겟 포탑 선정 함수
...
Tower findTarget() {
Tower choice = {0, 0, 0, 0, 0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Tower now = map[i][j];
if (now.atk == 0) continue;
if (choice.atk <= now.atk) {
if (choice.atk < now.atk)
choice = now;
else {
if (choice.last_turn > now.last_turn)
choice = now;
else if (choice.last_turn == now.last_turn) {
if (choice.row + choice.col > now.row + now.col)
choice = now;
else if (choice.row + choice.col == now.row + now.col) {
if (choice.col > now.col) choice = now;
}
}
}
}
}
}
return choice;
}
...- 문제에서 주어진 조건에 따라 완전 탐색으로 타겟 포탑을 찾는 함수
- 찾은 타겟 포탑 정보는
Tower구조체로 반환
레이저 경로 탐색 함수
...
void laser(int y, int x) {
struct Node {
int y, x;
};
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};
visited.assign(N, vector<int>(M, -1));
path.assign(N * M, {-1, -1, -1, -1, -1});
queue<Node> que;
que.push({y, x});
visited[y][x] = 0;
while (!que.empty()) {
Node now = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
// 경계를 벗어나는 경우 처리
if (ny < 0) {
ny = N - 1;
} else if (ny >= N) {
ny = 0;
}
if (nx < 0) {
nx = M - 1;
} else if (nx >= M) {
nx = 0;
}
// 파괴된 포탑이면 진입 불가
if (map[ny][nx].atk == 0) continue;
// 방문을 했는데, 더 빠른 경로였다면 스킵
if (visited[ny][nx] != -1 && visited[ny][nx] <= visited[now.y][now.x] + 1)
continue;
que.push({ny, nx});
visited[ny][nx] = visited[now.y][now.x] + 1;
path[map[ny][nx].id] = map[now.y][now.x];
}
}
}
...- 공격 포탑으로부터 타겟 포탑까지 최단 경로 탐색 (BFS 알고리즘 활용)
- 문제에서 주어진 조건에 따라 경계를 벗어나는 경로 처리 필수
- 탐색 우선 순서(오른쪽, 아래, 왼쪽, 위)에 맞춰 탐색 수행 ➡️ 경로 탐색의 우선 순위를 보장할 수 있음
- 최단 경로를 탐색함과 동시에 도착지(타겟 포탑)의 값이
-1이면 공격 불가 처리 가능 (이후 메인 함수에서 구분)
메인 함수 구현
...
int main() {
// 초기 입력
init();
// K번 턴 반복
for (int k = 0; k < K; k++) {
// 남은 타워가 1개라면, 즉시 종료
if (remain_tower == 1) break;
isAttack.assign(N * M, false);
// 공격자 선택
Tower attk = findAttacker();
attk.atk += (N + M);
attk.last_turn = k + 1;
isAttack[attk.id] = true;
// 타겟 선택
Tower target = findTarget();
isAttack[target.id] = true;
// 레이저 공격
laser(attk.row, attk.col);
...
}
...- 미리 선언한
init()함수로 초기 설정 (초기 입력) K번 반복 ➡️ 모두 반복하기 이전에 타워가 1개 남으면 종료 처리isAttack배열을 초기화함으로써 각 턴마다 공격 관여 여부 저장 준비 ➡️resize()를 사용하면 메모리 초과가 나올 수 있으니 주의!fildAttacker()함수와findTarget()함수를 이용하여 공격 포탑과 타겟 포탑 찾기laser()함수를 이용하여 레이저 공격 가능 여부와 최단 경로 탐색
레이저 공격 처리
...
int main() {
...
for (int k = 0; k < K; k++) {
...
// 레이저 공격이 가능하면,
if (visited[target.row][target.col] != -1) {
target.atk = target.atk - attk.atk;
if (target.atk <= 0) {
target.atk = 0;
isdestroy[target.id] = true;
remain_tower--;
}
map[target.row][target.col] = target;
// 경로에 있는 타겟 공격
int path_id = target.id;
while (1) {
Tower next = path[path_id];
if (next.id == attk.id) break;
next.atk = next.atk - (attk.atk / 2);
if (next.atk <= 0) {
next.atk = 0;
isdestroy[next.id] = true;
remain_tower--;
}
isAttack[next.id] = true;
map[next.row][next.col] = next;
path_id = next.id;
}
}
...
}
...- BFS에서 사용한 방문 배열을 이용하여 공격 가능 여부 확인 ➡️ 공격이 가능한 경우에만 레이저 공격 (불가능하면 포탄 공격)
- 타겟 포탑에 대한 처리를 마친 후, 경로에 있는 포탑 처리
- 경로가 저장된
path배열을 이용하여 거꾸로 탐색하며 경로 복기 및 조건에 따른 포탑 처리
- 경로가 저장된
포탄 공격 처리
...
int main() {
...
for (int k = 0; k < K; k++) {
...
else { // 레이저 공격 불가능하면,
target.atk = target.atk - attk.atk;
if (target.atk <= 0) {
target.atk = 0;
isdestroy[target.id] = true;
remain_tower--;
}
map[target.row][target.col] = target;
// 주변 공격
int dy[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
for (int i = 0; i < 8; i++) {
int ny = target.row + dy[i];
int nx = target.col + dx[i];
if (ny < 0)
ny = N - 1;
else if (ny >= N)
ny = 0;
if (nx < 0)
nx = M - 1;
else if (nx >= M)
nx = 0;
// 이미 파괴된 포탑이면 스킵
if (map[ny][nx].atk == 0) continue;
// 공격자이면 스킵
if (ny == attk.row && nx == attk.col) continue;
map[ny][nx].atk = map[ny][nx].atk - (attk.atk / 2);
if (map[ny][nx].atk <= 0) {
map[ny][nx].atk = 0;
isdestroy[map[ny][nx].id] = true;
remain_tower--;
}
isAttack[map[ny][nx].id] = true;
}
}
...- 레이저 공격이 불가능할 때, 포탄 공격 실행
- 포탄 공격은 타겟 포탐과 그 주위 8방향에 피해 ➡️ 단, 8방향 내에 공격 포탑이 존재하면, 공격 포탑은 공격을 받지 않음
- 레이저 공격과 마찬가지로, 공격을 받아 공격력이 0 이하로 떨어진 포탑에 대해 파괴 처리도 함꼐 진행 ➡️
isdestroy[tower.id] == true,remin_tower--,map[tower.row][tower.col].atk = 0
포탑 정비 처리
...
int main() {
...
for (int k = 0; k < K; k++) {
...
// 공격 포탑 처리
map[attk.row][attk.col] = attk;
// 공격 종료 후 정비
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j].atk == 0) continue;
if (isAttack[map[i][j].id]) continue;
map[i][j].atk += 1;
}
}
}
...- 공격이 마무리되면, 공격 포탑에 대한 정보를 map 배열에 할당 ➡️ 증가한 공격력에 대한 정보 반영
- 포탑 정비 처리 진행 ➡️ 공격과 무관한 포탑에 대해(
isAttack[tower.id] == false) 공격력 1씩 증가
남은 포탑 중 최대 공격력 찾기
...
int main() {
...
// 최대 값 찾기
int max_value = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (max_value < map[i][j].atk) {
max_value = map[i][j].atk;
}
}
}
cout << max_value;
return 0;
}- 모든 턴이 종료된 후, 남은 포탑들 중 최대값을 찾아 출력
전체 코드
#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Tower {
int id; // 임의의 포탑 ID
int row; // 위치좌표
int col;
int atk; // 공격력
int last_turn = 0; // 최근 공격한 turn
};
int N, M, K;
int remain_tower = 0;
vector<vector<Tower>> map; // 포탑 지도
vector<bool> isdestroy; // 파괴 여부 저장 (ID 기반)
vector<vector<int>> visited; // 최단 거리 (방문 여부)
vector<Tower> path; // 방문 경로 (ID 기반)
vector<bool> isAttack; // 공격 관여 여부
void init(); // 초기화 함수
Tower findAttacker(); // 공격자 탐색
Tower findTarget(); // 공격 타겟 탐색
void laser(int y, int x); // laser 공격 여부 BFS
int main() {
init();
// K번 턴 반복
for (int k = 0; k < K; k++) {
// 남은 타워가 1개라면, 즉시 종료
if (remain_tower == 1) break;
isAttack.assign(N * M, false);
// 공격자 선택
Tower attk = findAttacker();
attk.atk += (N + M);
attk.last_turn = k + 1;
isAttack[attk.id] = true;
// 타겟 선택
Tower target = findTarget();
isAttack[target.id] = true;
// 레이저 공격
laser(attk.row, attk.col);
// 레이저 공격이 가능하면,
if (visited[target.row][target.col] != -1) {
target.atk = target.atk - attk.atk;
if (target.atk <= 0) {
target.atk = 0;
isdestroy[target.id] = true;
remain_tower--;
}
map[target.row][target.col] = target;
// 경로에 있는 타겟 공격
int path_id = target.id;
while (1) {
Tower next = path[path_id];
if (next.id == attk.id) break;
next.atk = next.atk - (attk.atk / 2);
if (next.atk <= 0) {
next.atk = 0;
isdestroy[next.id] = true;
remain_tower--;
}
isAttack[next.id] = true;
map[next.row][next.col] = next;
path_id = next.id;
}
}
else { // 레이저 공격 불가능하면,
target.atk = target.atk - attk.atk;
if (target.atk <= 0) {
target.atk = 0;
isdestroy[target.id] = true;
remain_tower--;
}
map[target.row][target.col] = target;
// 주변 공격
int dy[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
for (int i = 0; i < 8; i++) {
int ny = target.row + dy[i];
int nx = target.col + dx[i];
if (ny < 0)
ny = N - 1;
else if (ny >= N)
ny = 0;
if (nx < 0)
nx = M - 1;
else if (nx >= M)
nx = 0;
// 이미 파괴된 포탑이면 스킵
if (map[ny][nx].atk == 0) continue;
// 공격자이면 스킵
if (ny == attk.row && nx == attk.col) continue;
map[ny][nx].atk = map[ny][nx].atk - (attk.atk / 2);
if (map[ny][nx].atk <= 0) {
map[ny][nx].atk = 0;
isdestroy[map[ny][nx].id] = true;
remain_tower--;
}
isAttack[map[ny][nx].id] = true;
}
}
map[attk.row][attk.col] = attk;
// 공격 종료 후 정비
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j].atk == 0) continue;
if (isAttack[map[i][j].id]) continue;
map[i][j].atk += 1;
}
}
}
// 최대 값 찾기
int max_value = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (max_value < map[i][j].atk) {
max_value = map[i][j].atk;
}
}
}
cout << max_value;
return 0;
}
void init() {
cin >> N >> M >> K;
map.resize(N, vector<Tower>(M));
isdestroy.resize(N * M, true);
int id = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Tower temp = {id, i, j, 0};
cin >> temp.atk;
if (temp.atk != 0) {
isdestroy[temp.id] = false;
remain_tower++;
}
map[i][j] = temp;
id++;
}
}
return;
}
Tower findAttacker() {
Tower choice = {0, 0, 0, INT_MAX, 0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Tower now = map[i][j];
if (now.atk == 0) continue;
if (choice.atk >= now.atk) {
if (choice.atk > now.atk)
choice = now;
else {
if (choice.last_turn < now.last_turn)
choice = now;
else if (choice.last_turn == now.last_turn) {
if (choice.row + choice.col < now.row + now.col)
choice = now;
else if (choice.row + choice.col == now.row + now.col) {
if (choice.col < now.col) choice = now;
}
}
}
}
}
}
return choice;
}
Tower findTarget() {
Tower choice = {0, 0, 0, 0, 0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Tower now = map[i][j];
if (now.atk == 0) continue;
if (choice.atk <= now.atk) {
if (choice.atk < now.atk)
choice = now;
else {
if (choice.last_turn > now.last_turn)
choice = now;
else if (choice.last_turn == now.last_turn) {
if (choice.row + choice.col > now.row + now.col)
choice = now;
else if (choice.row + choice.col == now.row + now.col) {
if (choice.col > now.col) choice = now;
}
}
}
}
}
}
return choice;
}
void laser(int y, int x) {
struct Node {
int y, x;
};
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};
visited.assign(N, vector<int>(M, -1));
path.assign(N * M, {-1, -1, -1, -1, -1});
queue<Node> que;
que.push({y, x});
visited[y][x] = 0;
while (!que.empty()) {
Node now = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
// 경계를 벗어나는 경우 처리
if (ny < 0) {
ny = N - 1;
} else if (ny >= N) {
ny = 0;
}
if (nx < 0) {
nx = M - 1;
} else if (nx >= M) {
nx = 0;
}
// 파괴된 포탑이면 진입 불가
if (map[ny][nx].atk == 0) continue;
// 방문을 했는데, 더 빠른 경로였다면 스킵
if (visited[ny][nx] != -1 && visited[ny][nx] <= visited[now.y][now.x] + 1)
continue;
que.push({ny, nx});
visited[ny][nx] = visited[now.y][now.x] + 1;
path[map[ny][nx].id] = map[now.y][now.x];
}
}
}결과
오답 원인
- 포탄 공격 시, 공격 포탑에 대한 예외 처리를 하지 않았음 ➡️ 항상 ⭐조건을 잘 체크⭐하며 구현하자!!
- 조금 더 함수로 나눴으면, 깔끔한 코드가 될 수 있었을 것 같아서 아쉬움