[APS][CodeTree] 삼성 SW 역량 테스트 2023년 상반기 오전 1번 문제

[APS][CodeTree] 삼성 SW 역량 테스트 2023년 상반기 오전 1번 문제 - 포탑 부수기📖 APS/CodeTree2025. 4. 12. 00:18@청월누리

Table of Contents

삼성 코딩테스트 기출 문제 설명: 포탑 부수기 | 코드트리

삼성전자 코딩테스트 기출 문제 포탑 부수기의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.

www.codetree.ai

문제

문제가 너무 길어서 생략... 위 링크에서 확인 가능합니다.

입력

출처 : https://www.codetree.ai/ko/frequent-problems/problems/destroy-the-turret/description

출력

풀이

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];
    }
  }
}

결과

오답 원인

포탄 공격 시, 공격 포탑에 대한 예외 처리를 하지 않았음 ➡️ 항상 ⭐조건을 잘 체크⭐하며 구현하자!!
조금 더 함수로 나눴으면, 깔끔한 코드가 될 수 있었을 것 같아서 아쉬움

'📖 APS > CodeTree' 카테고리의 다른 글

[APS][CodeTree] 삼성 SW 역량 테스트 2023년 상반기 오후 1번 문제 - 메이즈 러너 (0)	2025.04.12
[APS][CodeTree] 삼성 SW 역량 테스트 2023년 하반기 오전 1번 문제 - 왕실의 기사 대결 (0)	2025.04.12

@청월누리 :: DevKuk 개발 블로그

since 2025.01.27. ~ 개발자를 향해....🔥

문제

입력

출력

풀이

코드