[Algorithm]Baekjoon 17143 :: 낚시왕

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

17143번: 낚시왕

 
 
using namespace std;
 
struct Shark
{
    int y;
    int x;
    int speed;
    int dir;
    int size;
};
 
bool cmp(const Shark& a, const Shark& b)
{
    return a.size > b.size;
}
 
int height, width, sharkCount;
int arr[101][101] = { 0 };
vector<Shark> sharks;
int dirs[5][2] = { {0,0}, {-1,0}, {1,0}, {0,1}, {0,-1} };
int answer = 0;
 
void huntShark(int hunterColumn)
{
    for (int i = 1; i <= height; ++i)
    {
        if (arr[i][hunterColumn] > 0) // 상어있으면
        {
            answer += arr[i][hunterColumn];
            arr[i][hunterColumn] = 0; // 잡았다는 표시
            return;
        }
    }
}
 
void verticalMove(Shark& shark, int& count) // 수직이동
{
    if (shark.dir == 2) // 아래이동
    {
        if (count > height - shark.y) // 바닥에 부딪혀서 수면방향으로 바꿔야하면
        {
            count -= height - shark.y;
            shark.y = height; // 바닥에서부터 시작해서, count만큼 위로이동.
            shark.dir = 1; // 수면방향으로 변경
        }
        else
        {
            shark.y += count;
            count = 0;
        }
    }
    else // 위로 이동
    {
        if (count > shark.y - 1) // 수면에 부딪혀서 바닥방향으로 바꿔야하면
        {
            count -= shark.y - 1;
            shark.y = 1; // 수면첫위치로 변경.
            shark.dir = 2; // 바닥방향으로 변경
        }
        else
        {
            shark.y -= count;
            count = 0;
        }
    }
}
 
void horizontalMove(Shark& shark, int& count)
{
    if (shark.dir == 3) // 우측이동
    {
        if (count > width - shark.x) // 우측벽에 부딪혀서 좌측으로 다시 방향 틀어야하면
        {
            count -= width - shark.x; // 우측으로 이동한만큼 카운트 소모해주고
            shark.x = width; // 우측벽으로 위치이동.
            shark.dir = 4; // 방향전환.
        }
        else
        {
            shark.x += count;
            count = 0;
        }
    }
    else // 좌측이동
    {
        if (count > shark.x - 1) // 좌측벽에 부딪혀서 우측으로 다시 방향틀어야하면
        {
            count -= shark.x - 1;
            shark.x = 1; 
            shark.dir = 3; // 우측으로 방향변경
        }
        else
        {
            shark.x -= count;
            count = 0;
        }
    }
}
 
void moveShark(Shark& shark) 
{
    int count = shark.speed;
 
    if (shark.dir <= 2)
    {
        while (count > 0)
        {
            verticalMove(shark, count);
        }
    }
    else
    {
        while (count > 0)
        {
            horizontalMove(shark, count);
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> height >> width >> sharkCount;
 
    for (int i = 0; i < sharkCount; ++i)
    {
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;
 
        if (d <= 2) s %= (height * 2 - 2);
        else s %= (width * 2 - 2);
        sharks.push_back({ r,c,s,d,z });
        arr[r][c] = z;
    }
 
    sort(sharks.begin(), sharks.end(), cmp);
 
    for (int i = 1; i <= width; ++i) // 낚시왕 이동횟수.
    {
        huntShark(i);
 
        for (int j = 0; j < sharks.size(); ++j)
        {
            Shark& shark = sharks[j];
 
            if (arr[shark.y][shark.x] == 0) // 플레이어 사냥으로 잡혔으면
            {
                shark.size = -1; // 잡혔다는 표시해주기.
                continue;
            }
 
            if (shark.size == -1) continue; // 플레이어한테 잡혔던 상어이니, 지나치기
        
            arr[shark.y][shark.x] = 0;
            moveShark(shark);
        }
 
        for (int j = 0; j < sharks.size(); ++j)
        {
            Shark& shark = sharks[j];
            if (shark.size == -1) continue; // 폐기된 상어 건너뛰기
 
            if (shark.size < arr[shark.y][shark.x])
            {
                shark.size = -1; // 폐기
                continue;
            }
 
            arr[shark.y][shark.x] = shark.size;
        }
    }
 
    cout << answer;
}

 

거의 구현..느낌의 문제이다. 

 

상어의 이동을 잘~ 구현하는게 포인트.

 

먼저 상어들의 정보를 입력받을 때, arr에 상어들의 좌표에 해당상어의 크기를 전부 기록해놓는다.

그리고 중요한게, 136,137번째 라인을 보면 상어의 속력을 (해당 상어의 방향축 * 2 - 2)으로 나머지연산을 한게 보일것이다. 왜냐하면 모든 방향에 대해서, 해당축으로 해당축크기 * 2 - 2 만큼 이동할 경우, 반드시 같은방향,같은자리로 오게 되어있기 때문이다. 그렇기 때문에 나머지연산을 해줘서 불필요한 이동을 막아놓은 것이다.

위 나머지연산을 했을 경우 12ms가 나오고, 안할경우 48ms가 나왔다.

 

이후 매 초마다 일련의 로직을 수행하는데, 맨 처음엔 낚시꾼이 상어를 잡는것부터 시작한다.

낚시꾼이 있는 열의 위치에서 1~width의 행을 탐색하며 만나는 맨 처음 상어를 잡는다.

잡은 상어에 대해서는 해당 arr의 값을 0으로 표시해놓는다.

 

이후 모든 상어들의 이동을 수행해야 한다.

상어정보들이 들어있는 컨테이너를 순회하면서 이동을 시도할건데, 만약 수행 전 해당상어의 칸의 값이 0이라면, 바로 이전단계인 낚시왕의 사냥단계에서 낚시왕한테 잡혔다는 것이다.

그렇기 때문에 이제 이 상어는 더이상 검사할필요가 없다는 의미의 표시를 해두고 넘어간다. 나같은경우는 해당의미의 표시로 size값에 -1을 표시해놨다. 이후 또 검사할 때 size값이 -1이면 검사할필요 없으니 그냥 넘어가게하기 위해서이다.

-1값이 아니면 이동을 수행할건데, 수행전에 시작좌표값에 0을 넣어놓고 이동한다. 이제 이동할거니까 당연히 넣어놓는다.

 

실제 상어의 이동은 각각 네방향에 대해 전부 구현했다. 사실 여기서 시간을 좀 과하게 썼던게, 뭔가 하나의 식으로 4가지방향을 전부 커버할 수 있지 않을까... 하고 구상하다가 시간만 대차게 날려먹었다.

위 코드가 12ms 나오는데 8ms나오는분 코드보니까 기가막히게 잘 짜셨다. 코드량이 위코드의 절반정도밖에 안되는데... 

비트연산까지 있는거보니, 상당한 고수인 듯 했다.

 

상어들의 이동을 모두 끝마친 이후에 같은칸에 있는 상어들의 크기들을 비교해서, 가장 큰상어만이 살아남게 해야한다.

그것을 표현하기위해 일단 처음 주어지는 상어들의 정보를 크기를 기준으로 내림차순정렬을 했다.

상어들의 이동을 전부 마친후에, 한번 더 상어정보컨테이너를 순회하면서, 현재 선택되어진 상어의 위치에 있는 격자판의 값(해당 칸에있는 상어의 크기)이 현재 상어의 크기보다 크다면, 즉 현재 상어가 잡아먹혀야 한다면 표시를 해주고 넘어간다. 마찬가지로 표시는 size에 -1을 넣음으로써 표현했다.

그렇지 않다면 해당칸에 현재상어의 크기를 기록하면 된다.

 

이 로직을 수행할 때, 반드시 이전에 크기순으로 내림차순정렬을 해야한다. 

만약 오름차순이라면, 뒷부분의 상어가 앞부분의 상어를 잡아먹는다면 앞부분상어의 정보에 잡아먹혔다는 표시를 해야하는데, 앞부분상어의 정보를 따로 보관해놓지 않는다면 해당 상어의 인덱스를 알 수 없기 때문이다.

 

다만 쓰다보니 생각난거긴 한데, 어차피 상어는 최대 10,000마리이고 사이즈는 반드시 전부 다 다르기 때문에 

Shark check[10001]   <-- 이런식으로 관리할 수 있긴하다.

 

 

그리고 이동을 수행하는코드가 각각의 방향에 대해 작성해서 좀 마음에 안들었는데, 어떻게 하다보니 약간 공통되게 묶을 수 있었다. 

 

 
 
using namespace std;
 
 
 
int reverseDir(int dir)
{
    switch (dir)
    {
    case 1: return 2; break;
    case 2: return 1; break;
    case 3: return 4; break;
    case 4: return 3; break;
    default: return -100000;
    }
}
 
struct Shark
{
    int y;
    int x;
    int speed;
    int dir;
    int size;
    bool isPlusDir;
};
 
bool cmp(const Shark& a, const Shark& b)
{
    return a.size > b.size;
}
 
int height, width, sharkCount;
int arr[101][101] = { 0 };
vector<Shark> sharks;
int dirs[5][2] = { {0,0}, {-1,0}, {1,0}, {0,1}, {0,-1} };
int answer = 0;
 
void fishingShark(int hunterColumn)
{
    for (int i = 1; i <= height; ++i)
    {
        if (arr[i][hunterColumn] > 0) // 상어있으면
        {
            answer += arr[i][hunterColumn];
            arr[i][hunterColumn] = 0; // 잡았다는 표시
            return;
        }
    }
}
 
void moveShark(Shark& shark) 
{
    int count = shark.speed;
 
    while (count > 0)
    {
        int& standardAxisPos = shark.dir <= 2 ? shark.y : shark.x;
        int standardAxisSize = shark.dir <= 2 ? height : width;
        int first = shark.isPlusDir ? standardAxisSize : standardAxisPos;
        int second = shark.isPlusDir ? standardAxisPos : 1;
 
        if (count > first - second)
        {
            count -= first - second;
            standardAxisPos = shark.isPlusDir ? standardAxisSize : 1;
            shark.dir = reverseDir(shark.dir);
            shark.isPlusDir = !shark.isPlusDir;
        }
        else
        {
            standardAxisPos += shark.isPlusDir ? count : count * -1;
            count = 0;
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> height >> width >> sharkCount;
 
    for (int i = 0; i < sharkCount; ++i)
    {
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;
 
        if (d <= 2) s %= (height * 2 - 2);
        else s %= (width * 2 - 2);
 
        bool isPlusDir = d == 2 || d == 3 ? true : false;
 
        sharks.push_back({ r,c,s,d,z,isPlusDir });
        arr[r][c] = z;
    }
 
    sort(sharks.begin(), sharks.end(), cmp);
 
    for (int i = 1; i <= width; ++i) // 낚시왕 이동횟수.
    {
        fishingShark(i);
 
        for (int j = 0; j < sharks.size(); ++j)
        {
            if (arr[sharks[j].y][sharks[j].x] == 0) // 플레이어 사냥으로 잡혔으면
            {
                sharks[j].size = -1; // 잡혔다는 표시해주기.
                continue;
            }
 
            if (sharks[j].size == -1) continue; // 플레이어한테 잡혔던 상어이니, 지나치기
        
            arr[sharks[j].y][sharks[j].x] = 0;
            moveShark(sharks[j]);
        }
 
        for (int j = 0; j < sharks.size(); ++j)
        {
            if (sharks[j].size == -1) continue; // 폐기된 상어 건너뛰기
 
            if (sharks[j].size < arr[sharks[j].y][sharks[j].x])
            {
                sharks[j].size = -1; // 폐기
                continue;
            }
 
            arr[sharks[j].y][sharks[j].x] = sharks[j].size;
        }
    }
 
    cout << answer;
}
 

 

180라인가량 되던게 135정도까지 줄어들었다.

Shark 구조체에다가 해당 상어가 +방향으로 가는지, -방향으로 가는지 따로 저장을 함으로써 코드를 공통되게 묶을 수 있었다. 

결국 네가지방향이라는 것은 두 개의 축이 있고 각각의 축에 +,-방향이 있어서 네가지인데, 축은 dir <= 2의 검사로 쉽게 알아낼 수 있고 +인지 -인지는 따로 추가저장을 해놨기 때문에 바로 알 수 있게되어서, 삼항연산자를 통해 간결하게 묶을 수 있었다.

 

dirs는 안쓰는데 지우는걸 깜박했다.