[C++] BOJ 17837 - 새로운 게임 2

BOJ 17837 - 새로운 게임 2 (https://www.acmicpc.net/problem/17837)

 

01. 🔎 문제 탐색

N: 체스판 크기
K: 말의 개수
NxN 크기만큼 체스판의 각 칸의 색상을 입력
K개 말의 정보(x, y, 이동 방향)를 각각 입력

• 1개의 말 위에 다른 말을 올릴 수 있음
• 체스판의 칸 색상은 3종류 (흰색, 빨간색, 파란색)
  • 다음 칸이 흰색일 경우, 그대로 이동
  • 다음 칸이 빨간색일 경우, 말을 순서를 역순으로 바꾸어 이동
  • 다음 칸이 파란색(또는, 범위 밖)일 경우, 말의 이동 방향을 반대 방향(우 -> 좌, 위 -> 아래)로 바꾸어 이동
    • 만약, 방향을 바꾸어도 파란색일 경우, 아무 것도 수행하지 않고 넘김
• K개의 말을 체스판에 올리고 시작하며, 처음부터 말이 겹치는 경우는 없음
• 말의 이동 방향은 4가지 (오른쪽, 왼쪽, 위, 아래)
• 1턴은 K개의 말을 순서대로 이동시키는 것으로 증가
• 말이 이동할 때, 위에 쌓여진 모든 말들도 같이 이동함

* 종료 조건: 한 칸에 말이 4개 이상 쌓였을 경우,

01-1. 가능한 시간 복잡도 

• 시간 제한 0.5초로 5e7번의 연산까지 허용
• 각 이동에 대한 전수조사 시, 최악의 경우 1000*10^2로 1e5회의 연산 횟수로 O(1000*K^2) 시간 복잡도를 가짐

01-2. 알고리즘 선택

• 단순 시뮬레이션 문제, 전수조사로도 충분히 시간 내에 해결 가능

02. 📝 코드 설계하기

• 체스판을 나타내는 2차원 배열과 각 칸에 쌓인 말의 최대 높이를 나타내는 2차원 배열 사용
• 각 말은 현재 자신의 정보(위치, 이동 방향, 현재 높이)를 저장

1. N, K를 입력하고, 체스판 NxN에 대한 각 색상, K개 말의 정보(위치, 방향)를 입력받음
2. 반복문 내에 K개의 말의 이동을 수행하는 반복문을 수행
   1. 말의 정보를 받아 이동 수행
      1. 다음 칸이 흰색일 경우, 지금 말의 높이와 현재 칸의 말의 최대 높이를 비교하여 지금 말의 높이와 같거나 높은 말들을 전부 이동
      2. 다음 칸이 빨간색일 경우, 지금 말의 높이와 현재 칸의 말의 최대 높이를 비교하여 지금 말의 높이와 같거나 높은 말들을 전부 (현재 칸 최대 높이 + 다음 칸 최대 높이) - 현재 칸의 높이로 계산하여 이동
      3. 파란색일 경우, 방향을 반대로 바꾸고, 다음 칸의 색상을 계산 후, 이동 수행
         다시 파란색일 경우, 이동 명령 무시
   2. 이동 수행 완료 후, 현재 말이 위치한 칸의 말의 개수가 4개 이상일 경우, 반복을 종료하고 진행된 턴 횟수를 출력

03. 🛠️ 시도별 수정

1회차

• 정답은 나왔는데.. 너무 까막눈 코딩이라, 나중에 스택이랑 구조체를 이용해 말의 상태를 관리하는 방식으로 다시 구현해봐야겠다.

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

const short WHITE = 0;
const short RED = 1;
const short BLUE = 2;

int N, K;
vector<vector<int>> board(15, vector<int>(15));
vector<vector<int>> level(15, vector<int>(15, 0));

// tuple: {0: pos, 1: dir, 2: level}
vector<tuple<pair<int, int>, int, int>> cpu(11);

// l, r, u, d
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, 1, -1, 0, 0};

void move(pair<int, int> pos, int& dir, int lv){
  int x = pos.first, y = pos.second;
  int nx = x + dx[dir], ny = y + dy[dir];

  short color = BLUE;
  if(nx > 0 && nx <= N && ny > 0 && ny <= N) color = board[nx][ny];

  if(color == BLUE){ 
    if(dir % 2 != 0) dir += 1;
    else dir -= 1;

    nx = x + dx[dir], ny = y + dy[dir];
    if(nx > 0 && nx <= N && ny > 0 && ny <= N) color = board[nx][ny];
  }

  int diff;
  switch(color){
    case WHITE:
      diff = level[nx][ny] - lv;

      for(int i = 1; i <= K; i++){
        auto& cur_pos = get<0>(cpu[i]);
        auto& cur_lv = get<2>(cpu[i]);
        
        if(cur_pos.first == x && cur_pos.second == y){
          if(cur_lv >= lv){
            level[x][y]--;
            cur_pos = {nx, ny}; cur_lv = cur_lv + diff;
            level[nx][ny]++;
          }
        }
      }
    break;
    case RED:
      diff = level[x][y] - 1 + level[nx][ny];

      for(int i = 1; i <= K; i++){
        auto& cur_pos = get<0>(cpu[i]);
        auto& cur_lv = get<2>(cpu[i]);
        
        if(cur_pos.first == x && cur_pos.second == y){
          if(cur_lv >= lv){
            level[x][y]--;
            cur_pos = {nx, ny}; cur_lv = diff - cur_lv;
            level[nx][ny]++;
          }
        }
      }
    break;
  }
}

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

  cin >> N >> K;
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++) cin >> board[i][j];
  }

  for(int i = 1, a, b, c; i <= K; i++) {
    cin >> a >> b >> c;
    cpu[i] = {{a, b}, c, level[a][b]++};
  }

  int turn = 0;
  while(turn <= 1000 ){
    bool is_done = false;
    for(int i = 1; i <= K; i++){
      auto& pos = get<0>(cpu[i]);
      int& dir = get<1>(cpu[i]);
      int lv = get<2>(cpu[i]);

      move(pos, dir, lv);

      if(level[pos.first][pos.second] >= 4) {
        is_done = true;
        break;
      }
    }
    turn++;
    if(is_done) break;
  }

  if(turn > 1000) turn = -1;
  cout << turn << "\n";

  return 0;
}