[백준] 17143번 낚시왕

17143 낚시왕

문제

---

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.

3.상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

---

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

---

낚시왕이 잡은 상어 크기의 합을 출력한다.

---

풀이)

몇가지만 주의하면 되는 문제였다.

1. 한 칸에 상어가 2마리 이상있을 때, 1마리만 남기고 다 죽인다.

2. 낚시왕은 본인이 있는 열에서 가장 행이 작은 곳에 있는 상어만 잡는다.

처음에 풀 땐 한 칸에 여러 마리의 상어가 중복될 때를 해결 못해서 헤맸었다.

그래서 고민하다가 전체 맵을 int map[101][101]이 아닌,

vector <int> map[101][101]로 두고 모든 상어를 이동시킨 후

(상어가 이동한 칸에 상어 정보를 push)

map[][].size()가 2 이상인 칸에서 가장 큰 상어만 냅두고 나머지 상어를 제거해줬다.

과정은 이러하다.

1. 상어 정보를 저장하는 구조체 shark 선언.

   {상어 좌표 (y,x) , 속력 s , 이동 방향 d, 크기 z 저장됨.}

2. vector <shark>에 입력되는 상어 정보 저장.

   상어가 m마리 있으면, 0 ~ m - 1의 인덱스를 가지는 상어가 저장된다.

3. 낚시왕이 마지막 열까지 이동할 동안 while문 돌림.

   while 문 구조 {

① 낚시왕이 가장 가까운 상어 잡음.

 //상어 크기를 0으로 바꿈으로서 상어 제거

② 상어 위치 옮기기

//  for문으로 한 칸씩 옮기니깐 시간초과

//  상어가 자신의 원래방향을 유지한채 자기 자리로 돌아오는 횟수는 빼주기

③ map에 있는 모든 칸을 살펴보면서, 칸에 두마리 이상의 상어가 있으면 제거해주기

//  칸에 있는 상어를 크기순으로 내림차순 정렬하기

// 가장 큰 상어를 제외한 후, 상어 제거

//  상어 크기를 0으로 바꿈으로서 상어 제거

   }

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
struct shark {
    int r, c, s, d, z;
    shark(int r, int c, int s, int d, int z) {
        this->r = r;
        this->c = c;
        this->s = s;
        this->d = d;
        this->z = z;
    }
};
 
int r, c, m;
//위아래오른쪽왼쪽
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,1,-1 };
vector <int> map[101][101];
vector <shark> sh;
 
bool cmp(int a, int b) {
    return sh[a].z > sh[b].z;
}
 
bool check(int tr, int tc, int td) {
    if (tr + dr[td] < 1 || tr + dr[td] > r) return true;
    else if (tc + dc[td] < 1 || tc + dc[td] > c)return true;
 
    return false;
}
 
int main() {
    scanf("%d %d %d", &r, &c, &m);
 
    for (int i = 0; i < m; i++) {
        int r, c, s, d, z;
        scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
        sh.push_back({ r, c, s, d, z });
        map[r][c].push_back(i);
    }
 
    if (m == 0) { //상어가 한마리도 없으면
        printf("0");
        return 0;
    }
    int person = 1;//낚시왕의 위치
    int result = 0; //낚시왕이 죽인 상어의 합
 
    while (person <= c)
    {
        for (int i = 1; i <= r; i++) {
            if (map[i][person].size() == 0)continue;
 
            result += sh[map[i][person][0]].z;
            sh[map[i][person][0]].z = 0;
            map[i][person].clear();
            break;
        }
        //상어 위치 옮기기 전에 지우기
        for (int i = 0; i < sh.size(); i++) {
            if (sh[i].s == 0 || sh[i].z == 0) continue; //속력이 0이거나, 이미 죽은 상어면 pass
            map[sh[i].r][sh[i].c].clear();
        }
        //상어 위치 옮기기
        for (int i = 0; i < sh.size(); i++) {
            if (sh[i].s == 0 || sh[i].z == 0) continue; //속력이 0이거나, 이미 죽은 상어면 pass
 
            //for문으로 속력 하나씩 돌리니깐 시간이 너무 나옴
            //속력에서 상어가 자신의 원래방향을 유지한채 자기 자리로 돌아오는 값 빼주기
            int speed = sh[i].s;
            if (sh[i].d <= 2) {//상어 이동 방향이 상,하 이면
                int rotate = (r - 1) * 2;
                if (speed >= rotate) speed %= rotate;
                for (int j = 0; j < speed; j++) {
                    if (check(sh[i].r, sh[i].c, sh[i].d)) {//막다른 길에 부딪히면 방향바꾸기
                        if (sh[i].d == 1) {
                            sh[i].d = 2;
                        }
                        else {
                            sh[i].d = 1;
                        }
                    }
                    sh[i].r += dr[sh[i].d];
                    sh[i].c += dc[sh[i].d];
                }
            }
            else {//상어 이동 방향이 좌,우 이면
                int rotate = (c - 1) * 2;
                if (speed >= rotate) speed %= rotate;
                for (int j = 0; j < speed; j++) {
                    if (check(sh[i].r, sh[i].c, sh[i].d)) {//막다른 길에 부딪히면 방향바꾸기
                        if (sh[i].d == 4) {
                            sh[i].d = 3;
                        }
                        else {
                            sh[i].d = 4;
                        }
                    }
                    sh[i].r += dr[sh[i].d];
                    sh[i].c += dc[sh[i].d];
                }
            }
 
            map[sh[i].r][sh[i].c].push_back(i); //상어 이동 끝난 후 삽입
        }
 
        //같은 칸에 있는 상어 죽임
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                if (map[i][j].size() > 1) {
                    sort(map[i][j].begin(), map[i][j].end(), cmp);//크기순으로 내림차순
                    int live = map[i][j][0]; //살아 남은 상어 인덱스
                    for (int t = 1; t < map[i][j].size(); t++) {
                        sh[map[i][j][t]].z = 0;
                    }
                    map[i][j].clear();
                    map[i][j].push_back(live);
                }
            }
        }
        person++;
    }
 
    printf("%d", result);
 
    return 0;
}

결과)