BOJ 19237, 어른 상어

Source: BOJ 19237 어른 상어

어른 상어

변수를 어떻게 잡는냐가 관건이었던 문제였다

푸는데 3시간이 걸린건 안비밀..

문제를 요약해보자면 n x n 보드판위에 m 개의 상어가 있고 각각의 상어는 현재 방향과

다음칸으로 이동해야 할 때의 방향 우선순위를 가진다

방향: 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

상어는 방향 우선순위를 고려하여 빈칸으로의 이동을 우선순위로 갖고, 빈칸이 없다면 자신의 냄새가 있는 칸으로 이동한다

(마찬가지로 방향우선순위를 고려함)

만약 서로 다른 상어가 같은 한 칸에서 만나게 된다면 index가 작은 상어가 남고 다른 상어는 격자판 밖으로 나간다

PS Logic

1. SHARK라는 구조체를 만들고 그안에 priority라는 2차원 배열을 만들어 각 방향에 대한 다음방향 우선순위를 저장한다
2. 3차원 board를 만들고 각 칸안에 두개의 값 (상어의 number, 남은 유효시간)을 저장한다
3. 입력으로 주어지는 값들을 초기값으로 저장한다
4. while문 안에서 상어의 현재 위치, 방향을 찾고 그에 따른 다음위치, 다음 방향을 탐색한다
5. 다음 방향이 빈칸이라면 그 위치로 상어가 이동한다 (방향 우선순위 고려) (shark.x, shark.y, shark.dir 업데이트) (냄새 추가)
6. 인접한 칸에 빈칸이 없으면 상어는 자신의 냄새가 있는 칸으로 이동한다 (방향 우선순위 고려) (shark.x, shark.y, shark.dir 업데이트) (냄새 추가)
7. m개의 상어 중, 같은 좌표를 저장하고 있는 상어를 찾고 number가 큰 상어는 격자판 밖으로 제외시킨다
8. 보드판위에 모든 냄새가 있는 칸에 유효시간에 1을 뺀다
9. 현재 상어가 있는 칸도 1을 뺐으므로 현재 상어가 있는 칸은 1을 다시 더해줘야한다
10. 반복!

코드에 주석을 열심히 작성했으므로 주석을 보면서 코드를 참고하기 바란다

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
//위 아래 왼쪽 오른쪽
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct SHARK
{
  int x, y;
  int dir;
  int priority[4][4];
};
SHARK shark[401];

//상어 num 1~M, 1이 가장강함
//냄새 k번 이동하면 사라짐
int n, m, k;
int board[20][20][2]; // 상어의 NUM, 남은 유효시간

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> board[i][j][0];
      if (board[i][j][0] != 0)
      {
        board[i][j][1] = k;
        shark[board[i][j][0]].x = i;
        shark[board[i][j][0]].y = j;
      }
    }
  }
  // m개의 상어, 방향 입력
  for (int i = 1; i <= m; i++)
  {
    int d;
    cin >> d;
    d--;
    shark[i].dir = d;
  }
  //각 상어의 방향에 대한 우선순위 방향 입력
  for (int s = 1; s <= m; s++)
  {
    for (int i = 0; i < 4; i++)
    {
      for (int j = 0; j < 4; j++)
      {
        int dir;
        cin >> dir;
        dir--;
        shark[s].priority[i][j] = dir;
      }
    }
  }
  int test = 15;
  int time = 0;
  int flag = false;
  while (time <= 1000 && !flag)
  {
    time++;
    for (int s = 1; s <= m; s++)
    {
      //상어의 현재위치, 방향
      if (shark[s].x == -1)
        continue;
      int cx = shark[s].x;
      int cy = shark[s].y;
      int cd = shark[s].dir;
      bool empty = false;
      //상어의 다음위치, 방향
      for (int i = 0; i < 4; i++)
      {
        int nd = shark[s].priority[cd][i];
        int nx = cx + dx[nd];
        int ny = cy + dy[nd];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n)
          continue;
        if (board[nx][ny][0] == 0)
        {
          //상어의 이동 처리
          empty = true;
          shark[s].x = nx;
          shark[s].y = ny;
          shark[s].dir = nd;
          break;
        }
      }
      // 냄새가 있는 칸으로 이동
      if (!empty)
      {
        for (int i = 0; i < 4; i++)
        {
          int nd = shark[s].priority[cd][i];
          int nx = cx + dx[nd];
          int ny = cy + dy[nd];
          if (nx < 0 || ny < 0 || nx >= n || ny >= n)
            continue;
          if (board[nx][ny][0] == s && board[nx][ny][1]>0)
          {
            shark[s].x = nx;
            shark[s].y = ny;
            shark[s].dir = nd;
            break;
          }
        }
      }
    }
    //같은 칸에 있는 상어 처리
    for (int s = 1; s <= m; s++)
    {
      if(shark[s].x == -1) continue;
      int x = shark[s].x;
      int y = shark[s].y;
      for (int t = s + 1; t <= m; t++)
      {
        if (x == shark[t].x && y == shark[t].y)
        {
          shark[t].x = -1;
          shark[t].y = -1;
        }
      }
      board[shark[s].x][shark[s].y][0] = s;
      board[shark[s].x][shark[s].y][1] = k;
    }

    int cnt = 0;
    for(int s = 1; s<=m; s++){
      if(shark[s].x != -1) cnt++;
    }
    if (cnt == 1)
    {
      flag = true;
      break;
    }

     //냄새 유효시간 처리
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (board[i][j][1] == 0)
          {board[i][j][0] = 0;
          continue;}
        board[i][j][1]--;
        if(board[i][j][1] == 0){
          board[i][j][0] = 0;
        }
      }
    }
    //유효시간 전체를 1 뺐으므로 현재 상어가 있는칸은 1을 다시 더해줘야한다.
    for(int s = 1; s<=m; s++){
      board[shark[s].x][shark[s].y][1]++;
    }
  }
  int ans = 0;
  ans = (time>1000) ? -1 : time;
  cout << ans;
  return 0;
}