[BOJ] 29237 - 어른 상어

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

19237번: 어른 상어

 

난이도

구현 문제 / 난이도 ⭐️⭐️⭐️ / 디버깅이 아주 오래걸림.

 

주의할 점

보통 첫 번째 테스트케이스에 대한 시뮬레이션은 문제에 그림으로 제시되는 편인데, 모두 제시되어 있지 않아서 첫 번째 테스트 케이스 부터  막혔다.

 

1) 상어가  순차로 움직인다고 생각하면 안된다. 1번 상어가 갈 수 있는 경로를 탐색 후, 좌표를 움직여버리면, 2번 상어에 대한 경로를 탐색시 문제가 된다. 따라서

1번상어의 경로 탐색, 2번상어의 경로 탐색, 3번 상어의 경로 탐색 ... 탐색한 경로들은 따로 저장해두었다가 상어의 좌표를 한번에 움직인다.

 

2) 문제에 조건을 뺴먹어서 코드가 틀렸다고 생각했는데, 조건은 모두 숙지했으나 코드로 구현을 빼먹었다. 문제만 다시 읽느라고 시간낭비를 했다. (코드 check point 1 부분 참고)

 

3) 최초 문제 풀이 후 틀렸으면

문제 다시 읽기 -> printf찍지 말고 작성한 코드 검토 -> printf로 디버깅

 

4) main함수에 모두 풀지 말고 함수를 나눠서 작성해야 좋을 것 같다. (코드는 나중에 정리하겠다...ㅎ)

#include <stdio.h>
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

// 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.
int dirx[5] = {0, -1, 1, 0, 0};
int diry[5] = {0, 0, 0, -1, 1};
int timee;
int n, m, k;
int die_shark;

vector<int> move_shark(int shark_num, int sharkx, int sharky, vector<int> &cur_dir_arr, const vector<vector<vector<int> > > &dir_arr, vector<vector<pair<int, int> > > &check, vector<vector<int> > &sharks)
{
    int resultx = -1, resulty = -1, resultdir = -1;

    // dir_arr i: 상어번호, j: 현재 바라보는 방향, k: 현재 바라보고 있는 방향에서의 우선순위
    int new_dir;
    int cur_dir = cur_dir_arr[shark_num];
    int newx, newy;

    for (int i = 0; i < 4; i++)
    {
        new_dir = dir_arr[shark_num][cur_dir][i];

        newx = sharkx + dirx[new_dir];
        newy = sharky + diry[new_dir];

        if (newx < 0 || newy < 0 || newx > n - 1 || newy > n - 1)
        {
            continue;
        }

        if (check[newx][newy].first != 0)
        {
            if (abs(check[newx][newy].second - check[sharkx][sharky].second) >= k)
            {
                check[newx][newy].first = 0;
                check[newx][newy].second = 0;
            }
        }

        if (check[newx][newy].first == 0)
        {
            resultx = newx;
            resulty = newy;
            resultdir = new_dir;

            break;
        }
    }

    if (resultx == -1)
    {
        for (int i = 0; i < 4; i++)
        {
            new_dir = dir_arr[shark_num][cur_dir][i];

            newx = sharkx + dirx[new_dir];
            newy = sharky + diry[new_dir];

            if (newx < 0 || newy < 0 || newx > n - 1 || newy > n - 1)
                continue;

            if (check[newx][newy].first == shark_num)
            {
                resultx = newx;
                resulty = newy;
                resultdir = new_dir;

                break;
            }
        }
    }

    vector<int> result;
    result.push_back(shark_num);
    result.push_back(resultx);
    result.push_back(resulty);
    result.push_back(resultdir);

    return result;
}

bool compare(vector<int> v1, vector<int> v2)
{
    if (v1[0] < v2[0])
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);

    int temp;
    vector<vector<int> > sharks;
    vector<int> v;
    v.push_back(0);
    v.push_back(0);
    v.push_back(0);
    sharks.push_back(v);
    v.clear();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &temp);
            if (temp != 0)
            {
                v.push_back(temp);
                v.push_back(i);
                v.push_back(j);

                sharks.push_back(v);
                v.clear();
            }
        }
    }

    sort(sharks.begin(), sharks.end(), compare);

    vector<int> cur_dir(m + 1, 0);
    for (int i = 1; i < m + 1; i++)
    {
        scanf("%d", &cur_dir[i]);
    }

    vector<vector<vector<int> > > dir_arr(m + 1, vector<vector<int> >(5, vector<int>(4, 0)));
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j < 5; j++)
        {
            scanf("%d %d %d %d", &dir_arr[i][j][0], &dir_arr[i][j][1], &dir_arr[i][j][2], &dir_arr[i][j][3]);
        }
    }

    /* ----------------------- */
    timee = 0;
    vector<vector<pair<int, int> > > check(n, vector<pair<int, int> >(n, make_pair(0, 0)));
    for (int i = 1; i < sharks.size(); i++)
    {
        check[sharks[i][1]][sharks[i][2]].first = i;      // i번호 상어의 냄새를
        check[sharks[i][1]][sharks[i][2]].second = timee; // 0분에 뿌림
    }

    int shark_numm;
    int resultx;
    int resulty;
    int resultdir;
    while (1)
    {
        timee++;

        vector<vector<int> > results;

        for (int i = 1; i < sharks.size(); i++)
        {
            if (sharks[i][1] == -1 && sharks[i][2] == -1)
                continue;

            vector<int> result = move_shark(i, sharks[i][1], sharks[i][2], cur_dir, dir_arr, check, sharks);
            results.push_back(result);
        }

        for (int i = 0; i < results.size(); i++)
        {
            shark_numm = results[i][0];
            resultx = results[i][1];
            resulty = results[i][2];
            resultdir = results[i][3];

            if (resultx == -1)
                continue;

            if (check[resultx][resulty].first == 0 || check[resultx][resulty].first == shark_numm) // check point1) 뒤에 조건문 안써서 틀림.ㅠ
            {
                check[resultx][resulty].first = shark_numm;
                check[resultx][resulty].second = timee;

                sharks[shark_numm][1] = resultx;
                sharks[shark_numm][2] = resulty;
                cur_dir[shark_numm] = resultdir;
            }
            else if (check[resultx][resulty].first != 0)
            {
                sharks[shark_numm][1] = -1;
                sharks[shark_numm][2] = -1;
                die_shark += 1;
            }
        }

        if (abs(m - die_shark) == 1)
        {
            break;
        }

        if (timee == 1001)
        {
            break;
        }
    }

    if (timee == 1001)
    {
        printf("%d", -1);
    }
    else
    {
        printf("%d", timee);
    }
}