[백준][C++] 17143번 낚시왕

문제

문제 링크: https://www.acmicpc.net/problem/17143

 

 

난이도: 골드2

 

낚시왕은 R x C 격자판에서 1번부터 C번까지 가로 방향으로 매초마다 이동한다.

이때 같은 열, 가장 낮은 행에 있는 상어를 잡는다.

낚시왕이 상어를 잡고나면 상어는 각자의 방향과 속력으로 이동한다.

이때 벽에 부딪히면 반대 방향으로 방향을 바꾸어 남은 속력만큼 이동하고, 같은 칸에 2마리 이상의 상어가 있을 경우 크기가 가장 큰 상어만 남고 다른 상어는 잡아먹힌다.

이 과정을 반복하면서 최종적으로 낚시왕이 잡은 상어 크기의 합을 구하는 문제다.

 

---

문제 해결

 

이 문제는 시뮬레이션을 통해 구현할 수 있다.

각 상어마다 위치 좌표, 속력, 방향, 크기를 저장할 수 있도록 구조체를 정의하여 구현하였다.

 

처음에 상어를 이동시킬 때마다 같은 칸에 상어가 있는지 확인하여 큰 상어만 남도록 구현하였는데, 테스트 케이스와 여러 반례들을 다 통과하는데도 틀렸다고 나와서 꽤 오래 고민을 했다... (같은 문제를 겪은 블로그를 보고 문제점을 알 수 있었다)

같은 칸에 상어가 있는지 이동할 때마다 확인하면, 아직 이동하지 않은 상어까지 확인을 하게 되어 오답 처리가 된다. 따라서 우선 모든 상어를 모두 이동시켜준 후에 확인을 해주어야 했다.

 

또 한 가지 주의할 점은 상어의 속력이 최대 1000 이라는 점이다. 속력만큼 반복문을 통해 이동하게 되면 시간초과가 발생할 수 있다.

따라서 상어의 속력을 입력받을 때 유효한 속력을 계산해서 저장해야 한다. 

방향이 세로 방향(위, 아래)일 때는 2*(행의 크기-1)으로 나머지 연산을 하고, 가로 방향(오른쪽, 왼쪽) 일 때는 2*(열의 크기-1)로 나머지 연산을 하여 상어의 속력을 저장해주었다.

if(d < 3) s = s % (2*(r-1));	// 1위, 2아래
else s = s % (2*(c-1));		// 3오른쪽, 4왼쪽

---

소스코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct sharkInfo {
    int x, y, speed, d, size;
};

vector<int> board[102][102];
vector<sharkInfo> shark;
bool isDead[10010];
int r,c,m;
int dir[4][2] = {{-1,0}, {1,0}, {0,1}, {0,-1}}; // 위 아래 오른쪽 왼쪽

// 상어 이동
void sharkMove() {
    // m 마리 상어 이동
    for(int i=0; i<m; i++){

        // 상어가 죽은 경우
        if(isDead[i]) continue;

        int s = shark[i].speed; // 속력
        int &d = shark[i].d; // 방향
        int x = shark[i].x;
        int y = shark[i].y;

        // 속력만큼 이동
        int nx = x, ny = y;
        for(int j=0; j<s; j++) {
            nx += dir[d-1][0];
            ny += dir[d-1][1];

            // 경계를 넘는 경우 - 반대 방향으로 이동
            if(nx < 1 || nx > r || ny < 1 || ny > c) {
                nx -= dir[d-1][0];
                ny -= dir[d-1][1];

                if(d % 2 == 1) d++;
                else d--;
                nx += dir[d-1][0];
                ny += dir[d-1][1];
            }
        }

        // 이동
        board[x][y].erase(remove(board[x][y].begin(), board[x][y].end(), i), board[x][y].end());
        board[nx][ny].push_back(i);
        shark[i].x = nx;
        shark[i].y = ny;
    }
}

// 칸이 겹치는 상어 잡아먹기
void eatShark() {
    for(int i=0; i<m; i++) {
        if(isDead[i]) continue;

        int x = shark[i].x;
        int y = shark[i].y;

        if(board[x][y].size() > 1) {
            int biggestNum = board[x][y][0];
            int cnt = board[x][y].size();
            for(int j=1; j<cnt; j++) {
                int num = board[x][y][j];
                if(shark[num].size > shark[biggestNum].size) {
                    isDead[biggestNum] = true;
                    biggestNum = num;
                } else {
                    isDead[num] = true;
                }
            }
            board[x][y].clear();
            board[x][y].push_back(biggestNum);
        }
    }
}

int main() {
    cin >> r >> c >> m;
    memset(isDead, false, sizeof(isDead));
    for(int i=0; i<m; i++) {
        int x, y, s, d, z;
        cin >> x >> y >> s >> d >> z;
        board[x][y].push_back(i);
        if(d < 3) s = s % (2*(r-1));
        else s = s % (2*(c-1));
        shark.push_back({x, y, s, d, z});
    }

    int sum = 0;
    for(int i=1; i<=c; i++) {
        for(int j=1; j<=r; j++) {
            if(!board[j][i].empty()) {
                int num = board[j][i][0];
                sum += shark[num].size;
                isDead[num] = true;
                board[j][i].clear();
                break;
            }
        }
        sharkMove();    // 상어 이동
        eatShark();     // 칸이 겹치는 상어 잡아먹기
    }
    cout << sum << endl;
}