어른 상어

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

 

< 중요!>

반대로 생각을 해야한다.

냄새의 지속 시간이 줄어든다고 하지만

시간은 계속 증가한다. 이 시간을 변수로 쓰기 위해서는 

time + k를 저장해서 시간과 비교해야한다.

 

상어의 정보를 구조체에 넣자.

행, 열, 방향, live,

vector<int> priority[5] 

(이차원 벡터) -> 방향에 따른 우선순위 4방향 저장

 

이렇게 구조체에 넣자.

그리고 상어를 구조체 배열로 나타내자.

 

map도 구조체로 나타내야 한다.

1. vector<int> v

여러 상어가 한 칸에 있을 수 있으므로

2. smell_time

3. smell_host

 

순서

1. 냄새 뿌리기

2. 이동

3. 상어 죽이기

 

1. 냄새 뿌리기

k = 4이면 

1초에 뿌려지고 이 냄새는 5초에 없어진다.

그럼 smell_time에 5초가 저장

즉, time + k를 저장

 

2. 상어 이동

상어가 움직이려는 좌표가 가지고 있는 smell_time 값이

현재 시간보다 "작거나 같으면" 상어가 움직일 수 있다.

 

상어의 이동 전에

map[x][y].v.clear()를 해주고

for (int i = 1; i <= m; i++)

상어를 다 체크해가며 이동을 시켜준다.

 

3. 상어 죽이기 kill_shark()

map[x][y].v.size() >= 2일 때

일단 v를 sort해주고

(작은 애만 남기고 다 죽여야 하니까)

첫번째 원소를 저장하고

"1"부터 끝까지 shark의 live를 false로 바꾼다.

그리고

v.clear() 후 첫 번째 원소를 넣고

smell_host를 첫 번째 원소로 바꾼다.

 

4. main 함수

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다.

단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

 

상어가 1번 상어만 주어질 수도 있으므로

t = 0부터 순회해야한다!

t = 0부터 1000까지 for문을 돌리면서

setting_smell(t);

move_shark(t);

kill_shark();

를 순차적으로 진행

 

<소스 코드>

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
// 위, 아래, 왼쪽, 오른쪽
int dx[] = { 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, -1, 1 };
 
struct shark_info
{
    int row;
    int col;
    int dir;
    bool live;
    vector<int> priority[5];
};
 
struct map_info
{
    // 한 칸에 여러 상어가 있을 수 있으므로
    vector<int> v;
    int smell_time;
    int smell_host;
};
 
map_info map[25][25];
 
// 상어 최대 개수 400개
shark_info shark[410];
int ans;
 
int n, m, k;
 
void setting_smell(int jikan)
{
    for (int i = 1; i <= m; i++)
    {
        if (shark[i].live == false)
            continue;
 
        int x = shark[i].row;
        int y = shark[i].col;
        map[x][y].smell_time = jikan + k;
        map[x][y].smell_host = i;
    }
}
 
void move_shark(int jikan)
{
    for (int i = 1; i <= m; i++)
    {
        if (shark[i].live == false)
            continue;
        int x = shark[i].row;
        int y = shark[i].col;
 
        // 이제 움직이니까 v는 clear
        map[x][y].v.clear();
    }
 
    for (int i = 1; i <= m; i++)
    {
        if (shark[i].live == false)
            continue;
 
        int x = shark[i].row;
        int y = shark[i].col;
        int dir = shark[i].dir;
        // 자기 냄새의 위치, 방향
        int self_x, self_y, self_dir;
        self_x = self_y = self_dir = -1;
        bool flag = false;
 
        for (int j = 0; j < 4; j++)
        {
            int ndir = shark[i].priority[dir][j];
            int nx = x + dx[ndir];
            int ny = y + dy[ndir];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n)
            {
                // 아무 냄새가 없는 칸
                if (map[nx][ny].smell_time <= jikan)
                {
                    flag = true;
                    map[nx][ny].v.push_back(i);
                    shark[i].row = nx;
                    shark[i].col = ny;
                    shark[i].dir = ndir;
                    // 아무 냄새가 없는 칸에 갔다면 "종료"
                    break;
                }
                // 자기 냄새의 칸
                else
                {
                    if (map[nx][ny].smell_host == i)
                    {
                        // 한 번만 초기화
                        if (self_x == -1)
                        {
                            self_x = nx;
                            self_y = ny;
                            self_dir = ndir;
                        }
                    }
                }
            }
        }
 
        // 다 돌아보고 갈 곳이 없으면 자기 냄새의 위치로 간다.
        if (flag == false)
        {
            map[self_x][self_y].v.push_back(i);
            shark[i].row = self_x;
            shark[i].col = self_y;
            shark[i].dir = self_dir;
        }
    }
}
 
void kill_shark()
{
    for (int i = 1; i <= m; i++)
    {
        if (shark[i].live == false)
            continue;
 
        int x = shark[i].row;
        int y = shark[i].col;
 
        // 상어가 여러 마리
        if (map[x][y].v.size() >= 2)
        {
            // 가장 숫자 작은 애만 살아남음
            sort(map[x][y].v.begin(), map[x][y].v.end());
            int live_num = map[x][y].v[0];
            // 나머지는 죽인다
            for (int j = 1; j < map[x][y].v.size(); j++)
            {
                int shark_num = map[x][y].v[j];
                shark[shark_num].live = false;
            }
            map[x][y].v.clear();
            map[x][y].v.push_back(live_num);
            map[x][y].smell_host = live_num;
        }
    }
}
 
// 1번 상어만 살아있는지 체크하는 함수
bool check()
{
    for (int i = 2; i <= m; i++)
    {
        if (shark[i].live == true)
            return false;
    }
    return true;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int a; cin >> a;
            if (a != 0)
            {
                map[i][j].v.push_back(a);
                shark[a].row = i;
                shark[a].col = j;
            }
            map[i][j].smell_time = 0;
            map[i][j].smell_host = 0;
        }
    }
 
    for (int i = 1; i <= m; i++)
    {
        int dir;
        cin >> dir;
        shark[i].dir = dir;
        shark[i].live = true;
    }
 
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            int arr[4];
            cin >> arr[0] >> arr[1] >> arr[2] >> arr[3];
            for (int k = 0; k < 4; k++)
            {
                shark[i].priority[j].push_back(arr[k]);
            }
        }
    }
 
    // 상어가 한 마리 있을수도 있으므로 t = 0 부터 출발
    for (int t = 0; t < 1001; t++)
    {
        if (check() == true)
        {
            cout << t << '\n';
            return 0;
        }
        setting_smell(t);
        move_shark(t);
        kill_shark();
    }
 
    // 1000초를 넘었다면 -1 출력
    cout << -1 << '\n';
    return 0;
}