[APS][CodeTree] 삼성 SW 역량 테스트 2023년 하반기 오전 1번 문제 - 왕실의 기사 대결

삼성 코딩테스트 기출 문제 설명: 왕실의 기사 대결 | 코드트리

삼성 코딩테스트 기출 문제 설명: 왕실의 기사 대결 | 코드트리

---

문제

문제는 생략... 위 링크에서 확인 가능합니다.

입력

출처 : https://www.codetree.ai/ko/frequent-problems/problems/royal-knight-duel/description

출력

출처 : https://www.codetree.ai/ko/frequent-problems/problems/royal-knight-duel/description

---

풀이

• BFS(너비 우선 탐색) + 재귀 + 시뮬레이션(구현) 문제
• 주어진 조건을 빠짐없이 구현하는 것이 핵심 ➡️ 문제에서 주어진 기능 별로 함수로 구현하자!
  • init() : 배열 및 입력 정보 초기화
  • checkMovable() : 선택된 기사가 움직일 수 있는지 체크
  • move() : 조건에 따라 이동
  • dmgCheck() : 이동이 완료된 후 데미지 체크

---

코드

세부 코드 설명

필요한 변수 설정

...
struct Warrior {
  int id;
  int row;
  int col;
  int height;
  int width;
  int hp;
  int damage = 0;
  bool isLive = true;
};

int L, N, Q;  // 초기 입력값

vector<vector<int>> map;           // 맵 정보
vector<Warrior> warriors;          // 기사 정보
vector<vector<int>> warriors_map;  // 기사 배치 정보
vector<int> checkID;               // 이동가능 체크 여부
...

• struct Warrior : 구조체를 이용해 기사에 대한 정보 세팅 ➡️ 문제에서 주어지는 정보를 받을 수 있도록 세팅
  • id : 기사를 구분할 고유 번호 (1 ~ N까지의 번호로 구성)
  • row, col : 기사의 시작 좌표로, 기사가 차지하고 있는 밤위의 좌측 상단에 해당하는 좌표
  • height, width : 좌측 상단을 기준으로 기사가 차지하고 있는 범위
  • hp : 기사의 체력 (0 이하로 떨어지면 사망)
  • damage : 기사가 이동하면셔 누적된 피해량
  • isLive : 기사가 살아있는지 여부 체크 (default = true)

초기화

...
void init() {
  cin >> L >> N >> Q;

  map.resize(L + 2, vector<int>(L + 2, 2));
  warriors_map.resize(L + 2, vector<int>(L + 2, 0));

  for (int i = 1; i <= L; i++) {
    for (int j = 1; j <= L; j++) {
      cin >> map[i][j];
    }
  }

  for (int i = 0; i < N; i++) {
    int id = i + 1;
    int row, col, height, width, hp;
    cin >> row >> col >> height >> width >> hp;

    warriors.push_back({id, row, col, height, width, hp});

    for (int j = row; j < row + height; j++) {
      for (int k = col; k < col + width; k++) {
        warriors_map[j][k] = id;
      }
    }
  }
}
...

• 초기 입력 값으로 초기 세팅 진행
  • vector<vector<int>> map : 전체 지도 정보가 담긴 배열 ➡️ 이동 가능한 영역(0), 함정 위치(1), 벽 위치(2)로 구성
  • vector<vector<int>> warriors_map : 기사 배치 정보가 담긴 배열
  • vector<Warrior> warriors : 기사 정보가 담긴 배열
• map의 크기를 $ (L + 2) \times (L + 2) $ 로 세팅 ➡️ 맵의 좌표는 (1.1)에서 (L, L)까지로 이루어져 있고, 맵은 벽으로 둘러쌓여 있다는 조건이 있기 때문에 $ (L + 2) \times (L + 2) $로 세팅

명령 받은 기사가 이동 가능한지 체크

...
// 이동 가능 여부 체크 함수
bool checkMovable(int id, int dir) {
  // 이미 검사한 기사 체크 제외
  if (checkID[id - 1] == 1) return true;

  struct Warrior info = warriors[id - 1];
  checkID[id - 1] = 1;

  // 위쪽 이동 가능 여부 체크
  if (dir == 0) {
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.width; i++) {
      if (map[info.row - 1][info.col + i] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.width; i++) {
      if (warriors_map[info.row - 1][info.col + i] != 0) {
        int new_id = warriors_map[info.row - 1][info.col + i];

        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    return true;

  } else if (dir == 1) {  // 오른쪽 이동 가능 여부 체크
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.height; i++) {
      if (map[info.row + i][info.col + info.width] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.height; i++) {
      if (warriors_map[info.row + i][info.col + info.width] != 0) {
        int new_id = warriors_map[info.row + i][info.col + info.width];

        // 다음 기사가 죽어있으면 이동 가능
        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    // 모든 조건에 걸리지 않으면 이동 가능
    return true;
  } else if (dir == 2) {  // 아래쪽 이동 가능 여부 체크
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.width; i++) {
      if (map[info.row + info.height][info.col + i] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.width; i++) {
      if (warriors_map[info.row + info.height][info.col + i] != 0) {
        int new_id = warriors_map[info.row + info.height][info.col + i];

        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    return true;

  } else if (dir == 3) {  // 왼쪽 이동 가능 여부 체크
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.height; i++) {
      if (map[info.row + i][info.col - 1] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.height; i++) {
      if (warriors_map[info.row + i][info.col - 1] != 0) {
        int new_id = warriors_map[info.row + i][info.col - 1];

        // 다음 기사가 죽어있으면 이동 가능
        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    // 모든 조건에 걸리지 않으면 이동 가능
    return true;
  }

  return false;
}
...

• 명령으로 입력받은 기사의 ID와 이동 방향에 따라 이동 가능한지 체크
• 기사가 이동하는 방향에 다른 기사가 위치하고 있는 경우, 다른 기사도 이동 가능한지 체크해야 함 ➡️ 재귀를 이용하여 모두 탐색 진행
• 이동 가능 여부를 Boolean 타입으로 반환 ➡️ 이동 가능하면 true, 이동이 불가능하면 false 반환 ➡️ 재귀로 탐색이 진행되기 때문에 탐색 과정에서 한 명의 가사라도 이동이 불가능하면 이동 불가
• 재귀가 진행되는 동안, 어떤 기사가 이동했는지 체크하기 위해 vector<int> checkID 배열에 이동 가능 여부를 저장 ➡️ vector<int> 선언되어 있지만, index가 기사의 ID를 매칭하여 DAT로 작업 수행

기사의 이동

...
void move(int id, int dir, int comID) {
  if (dir == 0) {  // 위쪽 이동
    warriors[id - 1].row -= 1;
  } else if (dir == 1) {  // 오른쪽 이동
    warriors[id - 1].col += 1;
  } else if (dir == 2) {  // 아래쪽 이동
    warriors[id - 1].row += 1;
  } else if (dir == 3) {  // 왼쪽 이동
    warriors[id - 1].col -= 1;
  } else {
    return;
  }

  if (id != comID) {
    dmgCheck(id, warriors[id - 1].row, warriors[id - 1].col);
  }

  return;
}
...

• 이동이 가능하다면, 명령에 따라 이동이 필요한 모든 기사 이동 ➡️ main() 함수에서 반복문을 통해 checkID 배열에서 true 값을 가지는 기사만 이동 진행
• 기사의 위치의 기준이 되는 warrior.row와 warrior.col만 변경
• 이동한 기사가 명령을 받은 기사가 아니라면, 이동 후 받은 피해를 확인 ➡️ dmgCheck 함수 실행

움직인 기사에 대한 피해량 확인

...
void dmgCheck(int id, int row, int col) {
  int dy[] = {-1, 1, 0, 0};
  int dx[] = {0, 0, -1, 1};

  struct Node {
    int y, x;
  };

  vector<vector<int>> visited;
  visited.assign(L + 2, vector<int>(L + 2, 0));

  queue<Node> que;
  que.push({row, col});

  visited[row][col] = 1;

  int bomb = 0;  // 함정 개수 체크

  if (map[row][col] == 1) {
    bomb++;
  }

  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 (visited[ny][nx] != 0) continue;
      if (ny < row || nx < col || ny >= row + warriors[id - 1].height ||
          nx >= col + warriors[id - 1].width)
        continue;

      visited[ny][nx] = 1;
      que.push({ny, nx});

      if (map[ny][nx] == 1) {
        bomb++;
      }
    }
  }

  warriors[id - 1].damage += bomb;
  warriors[id - 1].hp -= bomb;

  if (warriors[id - 1].hp <= 0) {
    warriors[id - 1].isLive = false;
  }
}
...

• BFS를 통해 기사가 차지하는 칸((row, col) ~ (row + height, col + width))에 대해 함정 개수 체크 (✅ 지금 생각해보니...그냥이중 반복문으로도 확인이 가능하지 않을까 싶은데... 모르겠다..)
• 기사가 입은 피해량은 warrior.dmage에 누적되며, warrior.hp는 피해량 만큼 감소

메인 함수

...
int main() {
  init();

  for (int q = 0; q < Q; q++) {
    int id, dir;
    cin >> id >> dir;  // dir = 0, 1, 2, 3 (상, 우, 하, 좌)

    // 명령 받은 기사가 죽었으면, 다음 명령 입력으로...
    if (!warriors[id - 1].isLive) continue;

    // 살아 있으면 이동 가능한지 체크
    checkID.assign(N, 0);
    bool isMove = checkMovable(id, dir);

    // 이동 불가면 다음 명령 입력으로...
    if (!isMove) continue;

    // 이동 가능하면
    for (int i = 0; i < N; i++) {
      // 이동한 기사에 대해서 좌표 이동
      if (checkID[i] == 1) {
        move(i + 1, dir, id);
      }
    }

    // 이동이 끝났으면, 기사 배치도 다시 작성
    warriors_map.assign(L + 2, vector<int>(L + 2, 0));
    for (int i = 0; i < N; i++) {
      Warrior now = warriors[i];

      if (!now.isLive) continue;

      for (int j = now.row; j < now.row + now.height; j++) {
        for (int k = now.col; k < now.col + now.width; k++) {
          warriors_map[j][k] = now.id;
        }
      }
    }
  }

  int total_dmg = 0;
  for (int i = 0; i < N; i++) {
    if (!warriors[i].isLive) continue;

    total_dmg += warriors[i].damage;
  }

  cout << total_dmg;

  return 0;
}
...

• 지금까지 설계한 함수들을 문제에서 주어진 흐름과 조건에 맞게 배치
• 이동까지 모두 마무리되면, 기사 위치가 변경되었으므로 기사 위치에 대한 맵을 다시 작성 ➡️ 주어진 명령 개수(Q)만큼 전 과정 반복
• 모든 명령이 종료되면, 살아있는 기사들에 대해 누적된 총 피해량을 계산 후 출력

---

전체 코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Warrior {
  int id;
  int row;
  int col;
  int height;
  int width;
  int hp;
  int damage = 0;
  bool isLive = true;
};

int L, N, Q;  // 초기 입력값

vector<vector<int>> map;           // 맵 정보
vector<Warrior> warriors;          // 기사 정보
vector<vector<int>> warriors_map;  // 기사 배치 정보
vector<int> checkID;               // 이동가능 체크 여부

void init();                              // 초기화
bool checkMovable(int id, int dir);       // 이동 가능한지 체크
void move(int id, int dir, int comID);    // 이동
void dmgCheck(int id, int row, int col);  // 이동 후 데미지 체크

int main() {
  init();

  for (int q = 0; q < Q; q++) {
    int id, dir;
    cin >> id >> dir;  // dir = 0, 1, 2, 3 (상, 우, 하, 좌)

    // 명령 받은 기사가 죽었으면, 다음 명령 입력으로...
    if (!warriors[id - 1].isLive) continue;

    // 살아 있으면 이동 가능한지 체크
    checkID.assign(N, 0);
    bool isMove = checkMovable(id, dir);

    // 이동 불가면 다음 명령 입력으로...
    if (!isMove) continue;

    // 이동 가능하면
    for (int i = 0; i < N; i++) {
      // 이동한 기사에 대해서 좌표 이동
      if (checkID[i] == 1) {
        move(i + 1, dir, id);
      }
    }

    // 이동이 끝났으면, 기사 배치도 다시 작성
    warriors_map.assign(L + 2, vector<int>(L + 2, 0));
    for (int i = 0; i < N; i++) {
      Warrior now = warriors[i];

      if (!now.isLive) continue;

      for (int j = now.row; j < now.row + now.height; j++) {
        for (int k = now.col; k < now.col + now.width; k++) {
          warriors_map[j][k] = now.id;
        }
      }
    }
  }

  int total_dmg = 0;
  for (int i = 0; i < N; i++) {
    if (!warriors[i].isLive) continue;

    total_dmg += warriors[i].damage;
  }

  cout << total_dmg;

  return 0;
}

// 초기화 함수
void init() {
  cin >> L >> N >> Q;

  map.resize(L + 2, vector<int>(L + 2, 2));
  warriors_map.resize(L + 2, vector<int>(L + 2, 0));

  for (int i = 1; i <= L; i++) {
    for (int j = 1; j <= L; j++) {
      cin >> map[i][j];
    }
  }

  for (int i = 0; i < N; i++) {
    int id = i + 1;
    int row, col, height, width, hp;
    cin >> row >> col >> height >> width >> hp;

    warriors.push_back({id, row, col, height, width, hp});

    for (int j = row; j < row + height; j++) {
      for (int k = col; k < col + width; k++) {
        warriors_map[j][k] = id;
      }
    }
  }
}

// 이동 가능 여부 체크 함수
bool checkMovable(int id, int dir) {
  // 이미 검사한 기사 체크 제외
  if (checkID[id - 1] == 1) return true;

  struct Warrior info = warriors[id - 1];
  checkID[id - 1] = 1;

  // 위쪽 이동 가능 여부 체크
  if (dir == 0) {
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.width; i++) {
      if (map[info.row - 1][info.col + i] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.width; i++) {
      if (warriors_map[info.row - 1][info.col + i] != 0) {
        int new_id = warriors_map[info.row - 1][info.col + i];

        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    return true;

  } else if (dir == 1) {  // 오른쪽 이동 가능 여부 체크
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.height; i++) {
      if (map[info.row + i][info.col + info.width] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.height; i++) {
      if (warriors_map[info.row + i][info.col + info.width] != 0) {
        int new_id = warriors_map[info.row + i][info.col + info.width];

        // 다음 기사가 죽어있으면 이동 가능
        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    // 모든 조건에 걸리지 않으면 이동 가능
    return true;
  } else if (dir == 2) {  // 아래쪽 이동 가능 여부 체크
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.width; i++) {
      if (map[info.row + info.height][info.col + i] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.width; i++) {
      if (warriors_map[info.row + info.height][info.col + i] != 0) {
        int new_id = warriors_map[info.row + info.height][info.col + i];

        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    return true;

  } else if (dir == 3) {  // 왼쪽 이동 가능 여부 체크
    // 벽을 만나면 이동 불가
    for (int i = 0; i < info.height; i++) {
      if (map[info.row + i][info.col - 1] == 2) return false;
    }

    // 다른 기사를 만나면 다른 기사도 이동 가능한지 체크
    for (int i = 0; i < info.height; i++) {
      if (warriors_map[info.row + i][info.col - 1] != 0) {
        int new_id = warriors_map[info.row + i][info.col - 1];

        // 다음 기사가 죽어있으면 이동 가능
        if (!warriors[new_id - 1].isLive) continue;

        bool check = checkMovable(new_id, dir);
        if (!check) return false;
      }
    }

    // 모든 조건에 걸리지 않으면 이동 가능
    return true;
  }

  return false;
}

void move(int id, int dir, int comID) {
  if (dir == 0) {  // 위쪽 이동
    warriors[id - 1].row -= 1;
  } else if (dir == 1) {  // 오른쪽 이동
    warriors[id - 1].col += 1;
  } else if (dir == 2) {  // 아래쪽 이동
    warriors[id - 1].row += 1;
  } else if (dir == 3) {  // 왼쪽 이동
    warriors[id - 1].col -= 1;
  } else {
    return;
  }

  if (id != comID) {
    dmgCheck(id, warriors[id - 1].row, warriors[id - 1].col);
  }

  return;
}

void dmgCheck(int id, int row, int col) {
  int dy[] = {-1, 1, 0, 0};
  int dx[] = {0, 0, -1, 1};

  struct Node {
    int y, x;
  };

  vector<vector<int>> visited;
  visited.assign(L + 2, vector<int>(L + 2, 0));

  queue<Node> que;
  que.push({row, col});

  visited[row][col] = 1;

  int bomb = 0;  // 함정 개수 체크

  if (map[row][col] == 1) {
    bomb++;
  }

  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 (visited[ny][nx] != 0) continue;
      if (ny < row || nx < col || ny >= row + warriors[id - 1].height ||
          nx >= col + warriors[id - 1].width)
        continue;

      visited[ny][nx] = 1;
      que.push({ny, nx});

      if (map[ny][nx] == 1) {
        bomb++;
      }
    }
  }

  warriors[id - 1].damage += bomb;
  warriors[id - 1].hp -= bomb;

  if (warriors[id - 1].hp <= 0) {
    warriors[id - 1].isLive = false;
  }
}

---

결과

---

핵심 아이디어

• 기사의 이동 가능 여부를 어떻게 체크할 것인가? ➡️ 이동 가능 여부 체크 함수의 재귀를 통해 확인
• 이동한 후, 기사의 피해량(데미지)은 어떻게 측정할 것인가? ➡️ BFS를 이용한 탐색 진행