BOJ 17837, 새로운 게임2

Source: BOJ 17837 새로운 게임2

3일 동안 문제를 풀다가 결국 풀이를 보면서 해결한 문제..
문제에 대한 내용은 크기가 n x n인 체스판에 체스말들이 k개 있고, 각각의 체스말들을 체스말의 정해진 방향대로 움직이면서 다음의 규칙을 따른다
말이 이동하려는 칸이

1. 파란색이거나 벽일 경우
   • 방향을 반대로 바꿔서 진행
   • 다시 파란색이거나 벽일경우
     • 말은 움직이지 않는다.
       
2. 빨간색일 경우
   • 이동하려는 말들의 순서를 반대로 하여 이동한다.
3. 흰색일 경우
   • 그대로 그 칸으로 이동한다.

---

PS Logic

1. 판의 색깔을 저장하는 2차원배열 생성
2. POS라는 구조체를 만들어 pos라는 배열의 각 index에 체스말들의 정보를 저장
3. 체스판의 상태를 나타내는 MAP[12][12][5]를 선언하고 마지막 5개의 index에는 그 칸에 있는 체스말들의 순서를 나타낸다(MAP[12][12][0]은 그 칸의 말들의 개수)
4. int& “이름_size” = MAP[row][col][0]로 각칸의 체스말들의 개수가 변경되면 선언한 변수도 update가 될 수 있게 하는 것이 문제의 핵심

복습은 최고의 학습.. 같은문제가 나오면 바로 풀 수 있을만큼 반복 숙달을 해야겠다.

---

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

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int n, k;
int color[13][13]; //체스판의 색깔 저장
struct POS {
  int x, y;
  int d;
};
int MAP[12][12][5]; //체스판의 상태 저장
POS pos[10];  //체스 말들의 상태 저장하는 배열
int pos_size; //체스 말의 번호

int turn(int index){
  POS cur = pos[index];
  POS next;
  next.x = cur.x + dx[cur.d];
  next.y = cur.y + dy[cur.d];
  next.d = cur.d;
  //파란색 판이거나 벽에 만났을 때
  if(next.x<0 || next.y<0 || next.x >=n || next.y>=n || color[next.x][next.y] == 2){
    next.d = (cur.d==0 || cur.d==2) ? cur.d + 1 : cur.d - 1;
    next.x = cur.x + dx[next.d];
    next.y = cur.y + dy[next.d];
    pos[index].d = next.d;
    //다시한번 파란색 판이거나 벽에 만났을 때
    if(next.x<0 || next.y<0 || next.x >=n || next.y>=n || color[next.x][next.y] == 2){
      return MAP[cur.x][cur.y][0];
    }
  }

  //이동시켜야 할 체스 말들 파악
  int bottom = -1;
  int& cur_size = MAP[cur.x][cur.y][0];
  for(int i=1; i<=cur_size; i++){
    if(MAP[cur.x][cur.y][i] == index){
      bottom = i;
      break;
    }
  }
  //이동시켜야 할 체스 말들 저장
  int move[5] = {0, };
  int& move_size = move[0]; //움직여야 하는 말의 개수
  for(int i=bottom; i<=cur_size; i++){
    move[++move_size] = MAP[cur.x][cur.y][i];
  }
  cur_size = bottom - 1;

  //빨간색 판을 만났을 때 -> move 배열의 순서 뒤집어야 함
  if(color[next.x][next.y] == 1){
    for(int i=1; i<=move_size/2; i++){
      swap(move[i], move[move_size - i + 1]);
    }
  }

  //이동시켜야 할 체스말 이동
  int& next_size = MAP[next.x][next.y][0];
  for(int i=1; i<=move_size; i++){
    MAP[next.x][next.y][++next_size] = move[i];
    pos[move[i]].x = next.x;
    pos[move[i]].y = next.y;
    if(next_size >= 4){
      return next_size;
    }
  }
  return next_size;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>k;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>color[i][j];
    }
  }
  for(int i=0; i<k; i++){
    int x, y, d;
    cin>>x>>y>>d;
    x--, y--, d--;
    pos[pos_size].x = x;
    pos[pos_size].y = y;
    pos[pos_size].d = d;
    int& size = MAP[x][y][0];
    MAP[x][y][++size] = pos_size;
    ++pos_size;
  }
  int loop = 0;
  int ret = -1;
  while(loop<=1000 && ret == -1){
    loop++;
    for(int i=0; i<k; i++){
      int h = turn(i);
      if(h>=4){
        ret = loop;
        break;
      }
    }
  }
  cout<<ret;

  return 0;
}