[백준][구현] 17143 낚시왕 c++구현

목차

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

문제

 

문제 구현 방향

상어 구조체에 death를 추가했으면 더 쉽게 풀 수 있었던 문제인데 

배열에 넣고 담을려 해서 더 돌아갔다.

 

 

문제 아이디어

1. 속도 단위로 줄이기 

아래와 같이 상어는 갔다 돌아오는 것이므로 %연산자로 속도를 줄일 수 있다.

    for (auto& sh : v) {
        if (sh.direct <= 1) sh.S %= (2 * (R - 1));
        else
            sh.S %= (2 * (C - 1));
    }

 

2. 상어의 방향성 구현하기

아래와 같이 코드를 짜면 한번에 이동을 구현해 시간 초과가 나지 않는다.

끝에 도달할 경우를 잘 생각해 보면 while문안에서 최대 두번 돌고 구현할 수 있다.

 for (auto& sh : v) {
     int d = sh.direct;
     int x = sh.x;
     int y = sh.y;
     int s = sh.S;
     int nx, ny;
     while (1) {
         nx = x + dx[d] * s;
         ny = y + dy[d] * s;
         if (nx < C && ny < R && ny >= 0 && nx >= 0)break;
         if (d <= 1) {
             if (ny < 0) {
                 s -= y;
                 y = 0;
             }
             else {
                 s -= R - 1 - y;
                 y = R - 1;
             }
         }
         else {
             if (nx < 0) {
                 s -= x;
                 x = 0;
             }
             else {
                 s -= C - 1 - x;
                 x = C - 1;
             }
         }
         d ^= 1;
     }
     sh.x = nx;
     sh.y = ny;
     sh.direct = d;
 }

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<math.h>
#include<stack>

using namespace std;
int R, C, M;
int r, c, s, d, z;


typedef struct Shark {
    int x;
    int y;
    int S;
    int direct;
    int size;
};

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { -1, 1, 0, 0 };

Shark board[102][102];

vector<Shark> v;
int sum = 0;

void init() {
    Shark init = {
    -1, -1, -1, -1, -1
    };

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            board[i][j] = init;
        }
    }
}

void sharkCatching(int day) {
    vector<Shark> s;
    int flag = 1;
    Shark m = {
    day, 9999, -1, -1, -1
    };
    for (auto& p : v) {
        if (p.x == day) {
            if (p.y < m.y) {
                m = p;
            }
            flag = 0;
        }
    }
    if (flag)
        return;

    for (auto& p : v) {
        if (p.x == m.x && p.y == m.y)
            ;
        else
            s.push_back(p);
    }
    v = s;
    sum += m.size;
}

void sharkMoving() {
    vector<Shark> s;

    for (auto& sh : v) {
        int d = sh.direct;
        int x = sh.x;
        int y = sh.y;
        int s = sh.S;
        int nx, ny;
        while (1) {
            nx = x + dx[d] * s;
            ny = y + dy[d] * s;
            if (nx < C && ny < R && ny >= 0 && nx >= 0)break;
            if (d <= 1) {
                if (ny < 0) {
                    s -= y;
                    y = 0;
                }
                else {
                    s -= R - 1 - y;
                    y = R - 1;
                }
            }
            else {
                if (nx < 0) {
                    s -= x;
                    x = 0;
                }
                else {
                    s -= C - 1 - x;
                    x = C - 1;
                }
            }
            d ^= 1;
        }
        sh.x = nx;
        sh.y = ny;
        sh.direct = d;
    }

    init();
  
    for (auto& sh : v) {
        if (board[sh.y][sh.x].size !=-1) {
            if (board[sh.y][sh.x].size < sh.size)
                board[sh.y][sh.x] = sh;
        }
        else
            board[sh.y][sh.x] = sh;
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j].size != -1)
                s.push_back(board[i][j]);
        }
    }

    v = s;
    

}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> R >> C >> M;
    for (int i = 0; i < M; i++) {
        cin >> r >> c >> s >> d >> z;
        v.push_back({c-1, r-1, s, d-1, z});
    }
    for (auto& sh : v) {
        if (sh.direct <= 1) sh.S %= (2 * (R - 1));
        else
            sh.S %= (2 * (C - 1));
    }

    for (int i = 0; i < C; i++) {
        sharkCatching(i);

        sharkMoving();
    }
    cout << sum;


    
}