(C++) - 백준(BOJ) 17143번 : 낚시왕

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

17143번: 낚시왕

구현 문제였습니다.

 

 

📕 풀이방법

구조화, 갱신 시점을 꼼꼼히 처리해줘야합니다.

📔 입력 및 초기화

 1. 상어의 정보를 가지고 있는 구조체 Shark를 선언합니다.

 2. 각 상어의 정보를 가지고 있을 vector 변수 shark를 선언합니다. m을 입력받은 후 resize해줍니다.

 3. 낚시왕의 좌표를 저장할 구조체 King을 선언합니다. 이에 해당하는 변수는 fishKing입니다.

 4. 이차원 vector인 board변수를 선언합니다. 입력받은 r행 c열에 해당하는 상어의 정보가 저장됩니다.

 

📔 풀이과정

게임은 낚시왕이 c열을 벗어나면 끝납니다. 따라서 c번동안 아래의 함수를 한 번씩 실행합니다.

 

1. 낚시왕 이동 : fishKing의 c열을 1더해줍니다.

 

2. 낚시왕이 있는 열에서 가장 가까운 물고기 잡기 : 상어가 이동해도 가장 큰 상어가 나머지 작은 상어들을 다 잡아먹기 때문에 항상 r행 c열의 상어는 1마리입니다.

 

 2-1. 따라서 행을 검사해서 board[i][fishKing.c]의 size가 1이라면 바로 잡아줍니다.

 2-2. 잡았다면 정답을 출력할 catchCnt에 해당 상어의 크기를 더해줍니다.

 2-3. 이 후 낚시왕이 잡았기 때문에 해당 상어의 번호를 sharkNum에 저장한뒤 board[i][fishKing]을 clear()해줍니다.

 2-4. loop를 탈출합니다. 

 2-5. sharkNum이 0이상이라면 상어를 낚시왕이 잡았다는 뜻입니다. 따라서 shark를 확인해 잡힌 상어에 해당하는 번호에 접근해 erase해줘야합니다.

 

3. 상어 이동하기 : 한 칸씩 이동해도 시간초과가 나지 않기 때문에 공식을 세워 한 번에 가려고 하면 막중한 시간이 소모됩니다. 

 

 3-1. shark를 모두 확인하면서 이동 후의 좌표를 갱신해줍니다. 

 

 3-2. 상어는 처음 방향이 위 또는 아래였다면 계속 그 방향 또는 반대로만 왕복할 수 있습니다. 첫 방향이 좌, 우여도 마찬가지입니다. 이제 확인할 것은 위 또는 아래위치일 때 board를 벗어나는지 입니다. 현재 방향 * 상어의 속도가 이동 거리이므로 이 값만큼 loop를 돌며 다음을 확인합니다.

  3-2-1. 상어의 방향이 1(위)이고 현재 행의 위치가 1이면 방향을 2(아래)로 바꿔줍니다.

  3-2-2. 상어의 방향이 2(아래)이고 현재 행의 위치가 r이면 방향을 1(위)로 바꿔줍니다.

  3-2-3. 상어의 방향이 4(좌)이고 현재 행의 위치가 1이면 방향을 3(우)으로 바꿔줍니다.

  3-2-4. 상어의 방향이 3(우)이고 현재 행의 위치가 c이면 방향을 4(좌)으로 바꿔줍니다.

 

 3-3. 상어의 이동이 끝난 위치를 저장해줍니다.

 

4. 정보 갱신하기 : 한 칸에 2마리 이상의 상어가 있을 수 있기 때문에 shark와 board를 갱신해줍니다.

 4-1. r행c열의 board에 있는 상어를 clear()해줍니다.

 4-2. 3.에서 이동정보가 갱신된 상어들의 정보를 board에 모두 저장합니다.

 4-3. board를 모두 순회하며 두 마리 이상인 상어들에 대해 가장 큰 상어를 남기고 모두 clear해줍니다. 이는 정렬해서 i행 j열에 있는 상어를 크기에 대해 내림차순으로 정렬해준뒤 0번째 상어를 따로 저장한뒤에 i행j열의 board를 clear하고 다시 board[i][j]에 push_back함으로써 이뤄집니다.

 

📔 정답출력

 catchCnt를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int r, c, m, catchCnt;
struct Shark {int r, c, sp, d, sz, num; };
struct King {int r = 1, c = 0; } fishKing;
vector <Shark> board[101][101], shark;
// x, 상, 하, 우, 좌
int dr[] = {0,-1,1,0,0};
int dc[] = {0,0,0,1,-1};

bool cmp(Shark &a, Shark &b){
    return a.sz > b.sz; 
}

void moveFishKing(){
    fishKing.c++;
}

void updateStatus(){
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            board[i][j].clear();
            
    for(auto &s : shark) board[s.r][s.c].push_back(s);
    shark.clear();

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            if(!board[i][j].size()) continue;
            sort(board[i][j].begin(),board[i][j].end(),cmp);
            Shark biggestShark = board[i][j][0];
            board[i][j].clear();
            board[i][j].push_back(biggestShark);
            shark.push_back(biggestShark);
        }
    }
}


void catchClosestShark(){
    int sharkNum = -1;
    for(int i = 1; i <= r; i++){
        if(board[i][fishKing.c].size()){
            catchCnt += board[i][fishKing.c][0].sz;
            sharkNum = board[i][fishKing.c][0].num;
            board[i][fishKing.c].clear();
            break;
        }
    }

    if(sharkNum >= 0){
        for(auto s = shark.begin(); s != shark.end(); s++)
            if(s->num == sharkNum) { shark.erase(s); break; }
    }
}

void moveShark(){
    for(auto &s : shark){
        int nr = s.r;
        int nc = s.c;
        int iterRow = abs(dr[s.d] * s.sp);
        int iterCol = abs(dc[s.d] * s.sp);
        //위아래 초과
        for(int i = 0; i < iterRow; i++){
            if(nr == 1 && s.d == 1) s.d = 2;
            if(nr == r && s.d == 2) s.d = 1;
            nr += dr[s.d];
        }
        //좌우초과시 방향전환
        for(int i = 0; i < iterCol; i++){
            if(nc == 1 && s.d == 4) s.d = 3;
            if(nc == c && s.d == 3) s.d = 4;
            nc += dc[s.d];
        }
        s.r = nr;
        s.c = nc;
    }
}

int main(){
    cin >> r >> c >> m;
    shark.resize(m);
    for(int i = 0; i < m; i++){
        int r,c,s,d,z;
        cin >> r >> c >> s >> d >> z;
        shark[i] = {r,c,s,d,z,i};
        board[r][c].push_back(shark[i]);
    }

    for(int i = 1; i <= c; i++){
        moveFishKing();
        catchClosestShark();
        moveShark();
        updateStatus();
    }
    
    cout << catchCnt;
}