BOJ

BOJ::17143 낚시왕

BOJ Gold 3

BOJ::17143 낚시왕

[BOJ] : https://www.acmicpc.net/problem/17143

시사점

키

이해(x)

설계(x)

업데이트가 필요한 변수

시간 복잡도

공간 복잡도

구현(x)

#include<iostream>
#include<vector>
#include<algorithm>
const int MAX_N = 100 + 1;
const int MAX_SH = 100 * 100;
struct cell{ int x; int y; int s; int d; int z; };
const int nd[] = { 0, 2, 1, 4, 3 };
const int dx[] = { 0, -1, 1, 0, 0 }, dy[] = { 0, 0, 0, 1, -1 };
using namespace std;

int n, m, cntSh;
int a[MAX_N][MAX_N];
vector<cell> shark;
// 실수 : return (x == 1 || y == 1 || x == n || y == m); -> 방향에 위배되는 것만 넣어야하는데..
bool ontheLine(int x, int y, int d){
    if (d == 1 && x == 1) return true;
    if (d == 2 && x == n) return true;
    if (d == 3 && y == m) return true;
    if (d == 4 && y == 1) return true;
    return false;
}
void moveShark(int&x, int&y, int&d, int s){
    int nx = x, ny = y;
    // 와.. 예전에 한 실수를 또함.. 초기 위치부터 ontheLine에 있을 수 있으므로
    // 해당 if문 부터 실행 시킨 후에 -> dx, dy 더해줘야함.
    while (s--){
        if (ontheLine(nx, ny, d)){
            d = nd[d];
        }
        nx += dx[d], ny += dy[d];
    }
    x = nx, y = ny;
}
int simulate(){
    int column = -1, ret = 0;
    for (column = 1; column <= m; column++){
        // fishman kill the closest
        for (int i = 1; i <= n; i++)
            if (a[i][column] > 0){
                ret += a[i][column];
                // 상어 list에 사망 처리 해줘야함
                a[i][column] = 0;
                break;
            }

        // sharks move
        // map a에 있는 데이터 또 안지울뻔.. 하지만 이번엔 a는 버릴 것이므로 불필요
        int b[MAX_N][MAX_N] = { 0 };
        // for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)b[i][j] = 0;
        for (int i = 0; i < shark.size(); i++){
            // dead guys
            if (shark[i].z == 0 || a[shark[i].x][shark[i].y] != shark[i].z){
                shark[i].z = 0;
                continue;
            }
            int x = shark[i].x, y = shark[i].y, d = shark[i].d, s = shark[i].s, z = shark[i].z;
            int nx = x, ny = y, nd = d;
            moveShark(nx, ny, nd, s); // nx, ny, nd are updated
            shark[i].x = nx, shark[i].y = ny, shark[i].d = nd;
            b[nx][ny] = max(b[nx][ny], z);
        }
        for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)
            a[i][j] = b[i][j];
    }
    return ret;
}

int main(){
    freopen("input.txt", "r", stdin);
    cin >> n >> m >> cntSh;
    shark = vector<cell>(cntSh);
    for (int i = 0; i < cntSh; i++){
        cin >> shark[i].x >> shark[i].y >> shark[i].s >> shark[i].d >> shark[i].z;
        // 실수 (n-1) *2, (m-1) *2로 나눈 나머지 인데 *2를 각각 빼먹음
        if (shark[i].d <= 2) shark[i].s %= 2 * (n - 1);
        else shark[i].s %= 2 * (m - 1);
        a[shark[i].x][shark[i].y] = shark[i].z;
    }
    cout << simulate() << endl;
    return 0;
}
2nd try ( 60m ) 
#include<bits/stdc++.h>
#define endl '\n'
#define X first
#define Y second
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
struct cell{int x; int y; int spd;int d; int sz;};
const int MAXNM = 100;
const int dx[]={-1, 1, 0, 0}, dy[]={0, 0, 1, -1};
using namespace std;

int n, m, cntsh;
vector<cell> sh;
int a[MAXNM][MAXNM];
void onEdge(int& x, int& y, int & d){
    if(d == 0 && x == 0) d = 1;
    else if(d == 1 && x == n-1) d = 0;
    else if(d == 2 && y == m-1) d = 3;
    else if(d == 3 && y == 0) d = 2;
}

void input(){
    cin >> n >> m >> cntsh;
    rep(i, 0, cntsh){
        int x, y, spd, d, sz;
        cin >> x >> y >> spd >> d >> sz;
        d -= 1, x-=1, y-=1;
        // 실수(5) : n, m 바꿔씀
        if(d >= 2) spd = spd % ( (m-1) *2 ); // 실수(10) : 등호 안 넣음
        else spd = spd % ( (n-1) *2 );
        onEdge(x, y, d); // 실수(4) : 처음부터 벽보고 있을 수 있음, 따라서 해당 라인 추가해줌
        sh.push_back({x, y, spd, d, sz});
        a[x][y] = sz;
    }
}
void process(){
    int ans = 0;
    input();
    rep(fisher, 0, m){
        // fisher kill
        rep(i, 0, n) if(a[i][fisher] != 0){
            ans += a[i][fisher];
            a[i][fisher] = 0;
            break; // 실수(12) : break 안함
        }

        int b[MAXNM][MAXNM] = {0,};
        // shark move
        rep(i, 0, sh.size()) if(sh[i].sz != 0){
            if(a[sh[i].x][sh[i].y] != sh[i].sz){sh[i].sz = 0; continue;}
            int x = sh[i].x, y = sh[i].y, spd = sh[i].spd, &d = sh[i].d, &sz = sh[i].sz;
            int nx = x, ny = y;
            while(spd--){
                nx += dx[d], ny += dy[d];
                onEdge(nx, ny, d);
            }
            // cmp
            if(b[nx][ny] < sz){
                b[nx][ny] = sz;
            }else sz = 0;

            // De-init ( 불필요 )
            // init
            sh[i].x = nx, sh[i].y = ny;
        }
        memcpy(a, b, sizeof(a));
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

디버깅(x)

2nd try

  • 입력받아서 speed의 값을 축소시켜주는 작업을 할때, n과 m을 바꿔서 사용했습니다. (5m)
  • speed의 값을 축소시키는 것은, 방향에 따라 달라집니다. ( 10m )
    • 방향을 0,1과 2,3으로 나눠야 하지만 d>2 와 else로 사용했습니다.
  • 처음부터 상어가 벽을 보고 있는 경우에 대한 처리를 해주지 않았습니다. ( 4m )
  • process함수에서 낚시꾼이 가장 가까운 상어를 잡으면 break해주어야 하지만 처리해주지 않았습니다. (12m)

좋은 코드

최적화