마법사 상어와 복제

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

23290번: 마법사 상어와 복제

결국은 다 기출이었다.
1. 물고기 복제
4 × 4 크기의 격자
격자 크기 엄청 작다.
O(N^2)도 전혀 문제 없을듯.

 

물고기의 정보를 저장하는
구조체 벡터를 만들자.

2. 둘 이상의 물고기가 같은 칸에 있을 수도 있다.
벡터 배열을 사용해서 달자.

// 물고기의 방향을 저장한다.

vector<int> fish_map[5][5];

 

3. fish_move(int t)

vector<f_info> tmp;

 

2중 for 문 돌리면서

fish_map[i][j] != 0이면

vector<int> v = fish_map[i][j];

fish_map[i][j].clear();

 

for(int k = 0; k < v.size(); k++)

    이동 성공

    tmp.push_back({nx, ny, dir});

    이동 실패

    tmp.push_back({x, y, first_dir});

 

마지막에 다시 fish_map에 넣어준다.

for(int i = 0; i < tmp.size(); i++)

     fish_map[tmp[i].row][tmp[i].col].push_back(tmp[i].dir);

 

4. void shark_move(int t)

4 ^ 3 = 64가지밖에 안된다..

재귀 쓰지말고 그냥 3중 for문으로 돌려버리자

 

(x, y) -> (nx, ny) -> (nnx, nny) -> (nnnx, nnny)

 

주의!!! 중복으로 먹으면 안된다!

if(nnx == nx && nny == ny)

      t_cnt = 0;

 

구조체 비교 연산으로

가장 많이 먹는 (같다면 사전 순으로 앞에오는)

좌표들을 구했다면

 

1번 턴에 먹히면 4번턴에 냄새가 사라지므로!

fish_smell[][] = t+ 3;

fish_map[][].clear();

<소스 코드>

#include <iostream>
#include <cstring>
#include <vector>
 
using namespace std;
 
int m, s;
 
int f_dx[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int f_dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
 
// 상, 좌, 하, 우
int s_dx[] = { -1, 0, 1, 0 };
int s_dy[] = { 0, -1, 0, 1 };
 
struct s_wichi {
    int row;
    int col;
};
 
s_wichi shark;
 
struct f_info {
    int row;
    int col;
    int dir;
};
 
// 방향이 들어간다
vector<int> fish_map[5][5];
 
 
// 냄새가 사라지는 시간을 기록하자
// 1에 생기면 4부터 사용 가능
// t + 3
int fish_smell[5][5];
 
void fish_move(int t)
{
    vector<f_info> tmp;
 
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            if (fish_map[i][j].size() == 0)
                continue;
 
            // 벡터 저장
            vector<int> v = fish_map[i][j];
 
            fish_map[i][j].clear();
 
            for (int k = 0; k < v.size(); k++)
            {
                int x = i;
                int y = j;
                int first_dir = v[k];
                int dir = v[k];
 
                int cnt = 9;
 
                while (cnt > 0)
                {
                    int nx = x + f_dx[dir];
                    int ny = y + f_dy[dir];
 
                    // 범위 벗어남
                    if (nx < 1 || nx > 4 || ny < 1 || ny > 4)
                    {
                        cnt--;
                        dir--;
                        if (dir == -1)
                            dir = 7;
 
                        continue;
                    }
 
                    if (fish_smell[nx][ny] > t || (shark.row == nx && shark.col == ny))
                    {
                        cnt--;
                        dir--;
                        if (dir == -1)
                            dir = 7;
 
                        continue;
                    }
 
                    // 다 통과했다면 이동 가능
                    tmp.push_back({ nx, ny, dir });
                    break;
                }
 
                // 움직이지 못했다
                if (cnt == 0)
                    tmp.push_back({ x,y,first_dir });
            }
        }
    }
 
    for (int i = 0; i < tmp.size(); i++)
    {
        f_info f = tmp[i];
        fish_map[f.row][f.col].push_back(f.dir);
    }
}
 
 
struct shark_doko {
    int how_many;
    int dict;
};
 
bool operator < (const shark_doko& a, const shark_doko& b)
{
    if (a.how_many == b.how_many)
        return a.dict > b.dict;
    return a.how_many < b.how_many;
}
 
 
// 이건 재귀를 써볼까? 별로
// 64가지 방법을 그냥 3중 for문 돌자
void shark_move(int t)
{
    int gijun_x = shark.row;
    int gijun_y = shark.col;
 
    shark_doko ans_doko = { 0, 500 };
    shark_doko tmp_doko;
 
    pair<int, int> ichi;
    pair<int, int> ni;
 
 
    for (int a = 0; a < 4; a++)
    {
        int nx = gijun_x + s_dx[a];
        int ny = gijun_y + s_dy[a];
 
        // 못 감
        if (nx < 1 || nx > 4 || ny < 1 || ny > 4)
            continue;
 
        int bak = 100 * (a + 1);
        int f_cnt = fish_map[nx][ny].size();
 
        for (int b = 0; b < 4; b++)
        {
            int nnx = nx + s_dx[b];
            int nny = ny + s_dy[b];
 
            // 못 감
            if (nnx < 1 || nnx > 4 || nny < 1 || nny > 4)
                continue;
 
            int sip = 10 * (b + 1);
            int s_cnt = fish_map[nnx][nny].size();
 
            for (int c = 0; c < 4; c++)
            {
                int nnnx = nnx + s_dx[c];
                int nnny = nny + s_dy[c];
 
                // 못 감
                if (nnnx < 1 || nnnx > 4 || nnny < 1 || nnny > 4)
                    continue;
 
                int ill = (c + 1);
                int t_cnt = fish_map[nnnx][nnny].size();
 
                // 중복으로 먹는거는 안됨
                if (nnnx == nx && nnny == ny)
                {
                    t_cnt = 0;
                }
 
                // 끝까지 왔다면? 비교
                tmp_doko = { f_cnt + s_cnt + t_cnt, bak + sip + ill };
                if (ans_doko < tmp_doko)
                {
 
                    ans_doko = tmp_doko;
                    ichi = { nx, ny };
                    ni = { nnx, nny };
                    shark.row = nnnx;
                    shark.col = nnny;
                }
            }
        }
    }
 
    if (fish_map[ichi.first][ichi.second].size() != 0)
        fish_smell[ichi.first][ichi.second] = t + 3;
 
    fish_map[ichi.first][ichi.second].clear();
 
    if (fish_map[ni.first][ni.second].size() != 0)
        fish_smell[ni.first][ni.second] = t + 3;
 
    fish_map[ni.first][ni.second].clear();
 
    if (fish_map[shark.row][shark.col].size() != 0)
        fish_smell[shark.row][shark.col] = t + 3;
 
    fish_map[shark.row][shark.col].clear();
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    memset(fish_smell, 0, sizeof(fish_smell));
 
    cin >> m >> s;
 
    // 초기화
    for (int i = 1; i <= m; i++)
    {
        int x, y, d;
        cin >> x >> y >> d;
        fish_map[x][y].push_back(d - 1);
    }
 
    cin >> shark.row >> shark.col;
 
    vector<f_info> boksa;
 
    for (int turn = 1; turn <= s; turn++)
    {
        boksa.clear();
        for (int i = 1; i <= 4; i++)
        {
            for (int j = 1; j <= 4; j++)
            {
                if (fish_map[i][j].size() != 0)
                {
                    for (int k = 0; k < fish_map[i][j].size(); k++)
                    {
                        boksa.push_back({ i,j, fish_map[i][j][k] });
                    }
                }
            }
        }
 
        fish_move(turn);
        shark_move(turn);
 
        for (int i = 0; i < boksa.size(); i++)
        {
            fish_map[boksa[i].row][boksa[i].col].push_back(boksa[i].dir);
        }
    }
 
    int ans = 0;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            ans += fish_map[i][j].size();
        }
    }
 
    cout << ans << '\n';
    return 0;
}