어른 상어

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0615 ~ 0810
int ans;
int dx[4] = {0, 0, -1, 1}; // 위 아래 왼쪽 오른쪽
int dy[4] = {-1, 1, 0, 0};
int board[25][25];
int t_board[25][25];
pair<int,int> pheromone[25][25]; // 상어 번호, 남은 시간
pair<int,int> t_pheromone[25][25];
struct shark{
    int y;
    int x;
    int dir;
};
vector<int> shark_pri[4][410]; // dir,상어번호
vector<shark> shark_v(410); // 1번상어 -> 1번 인덱스
int N,M,k;
int saveDir(int d){
    if(d > 3) d-=4;
    if(d < 0) d+=4;
    return d;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> k;
    /* board정보 & 상어 위치 & 초기 페로몬 정보 저장 */
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 0) continue;
            shark_v[board[i][j]].y = i;
            shark_v[board[i][j]].x = j;
            pheromone[i][j] = {board[i][j], k}; // 최초 k만큼 지속
        }
    /* 상어의 최초 방향을 저장 */
    for(int i=1;i<=M;i++)
    {
        int d;
        cin >> d;
        shark_v[i].dir = d-1;
    }
    /* 상어의 방향마다 우선순위를 받는다 */
    for(int i=1;i<=M;i++)
    {
        for(int j=0;j<4;j++)
        {
            int p1,p2,p3,p4;
            cin >> p1 >> p2 >> p3 >> p4;
            shark_pri[j][i].push_back(p1-1);
            shark_pri[j][i].push_back(p2-1);
            shark_pri[j][i].push_back(p3-1);
            shark_pri[j][i].push_back(p4-1);
        }
    }
    while(true)
    {
        ans++;
        /* 상어 이동 */
        for(int i=1;i<=M;i++)
        {
            bool empty_space = false;
            auto cur = shark_v[i];
            if(cur.y == -1) continue;
            for(int n=0;n<4;n++)
            {
                int ndir = shark_pri[cur.dir][i][n];
                int ny = cur.y + dy[ndir];
                int nx = cur.x + dx[ndir];
                if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
                if(pheromone[ny][nx].second > 0) continue;
                // 내가 갈 곳에 이미 상어가 있는데 내가 더 번호가 크면 나는 집에 가야함
                if(t_board[ny][nx] != 0 and t_board[ny][nx] < i){
                    empty_space = true;
                    shark_v[i].y = -1;
                    shark_v[i].x = -1;
                    shark_v[i].dir = -1;
                    break;
                }
                t_pheromone[ny][nx] = {i, k};
                shark_v[i].y = ny;
                shark_v[i].x = nx;
                shark_v[i].dir = ndir;
                t_board[ny][nx] = i;
                empty_space = true;
                break;
            }
           if(empty_space == true) continue;
            /* 페로몬이 없는칸이 없으므로 우선순위에 따라 내 페로몬이 있는 곳으로 이동 */
            for(int n=0;n<4;n++)
            {
                int ndir = shark_pri[cur.dir][i][n]; // 우선순위에 따르는 특별한 dir
                int ny = cur.y + dy[ndir];
                int nx = cur.x + dx[ndir];
                if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
                if(pheromone[ny][nx].first != i) continue; // 내 페로몬이 없으면 pass
                t_pheromone[ny][nx] = {i, k};
                shark_v[i].y = ny;
                shark_v[i].x = nx;
                shark_v[i].dir = ndir;
                t_board[ny][nx] = i;                        
                break;
            }
        }
        /* t_pheromone -> pheromone 으로 이동 */
        /* 페로몬 감소 */
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
            {
                if(pheromone[i][j].second == 0) continue;
                pheromone[i][j].second--;
                if(pheromone[i][j].second == 0)
                    pheromone[i][j] = {0, 0};
            }
        /* 새롭게 추가된 페로몬을 복사 */
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
            {
                if(t_pheromone[i][j].second == 0) continue;
                pheromone[i][j] = t_pheromone[i][j];
                t_pheromone[i][j] = {0,0}; // 초기화
            }
        /* t_board -> board로 이동 */
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
            {
                board[i][j] = t_board[i][j];
                t_board[i][j] = 0;
            }
        /* 1번 상어만 남았는지 검사 */
        int cnt=0;
        for(int i=1;i<=M;i++)
            if(shark_v[i].y != -1) cnt++;
        if(cnt == 1) break;
        else if(ans >= 1000){
            ans = -1;
            break;
        }
    }
    cout << ans;
    return 0;
}

• 핵심
  • 동시에 일어나는 일이기 때문에 비어있는 임시배열을 이용하는 것
    : board[][]와 pheromone[][]으로 비교 t_board[][]와 t_pheromone[][]에 저장
  • 상어의 정보를 응집하기 위해 shark 구조체 사용

• 이상한 점
  : 해당 문제에서 1000이 넘으면 종료된다고 문제에 나와있으나 1000이 되어도 -1로 처리를 해야함
  --> 많은 사람들이 이것으로 오답처리 됨