[백준] 17143 - 낚시왕

얼마전 있었던 모 기업의 코딩테스트 기출이라길래 풀어보았는데....

이 문제 말고 같은 시간대의 시험이 두 문제 모두 시뮬레이션이 나오는 건 처음봤다...

두 문제 합쳐서 디버깅까지 내가 2시간이 걸렸다면.... 할만 했다고 생각...

개인적으로 구현이 쬐끔 까다로울 뿐 그리 어려운 문제는 아니었다고 생각한다

1. 일단 물고기들의 좌표를 구조체 배열에 저장하며, map에는 그 물고기들의 index(입력 순서 i값)을 찍어준다

2. 물고기를 문제의 조건에 맞게 시간에 따라 x축을 하나씩 이동하며 y축을 검사하고, 물고기를 잡는다

- 물고기를 잡았다면 그 해당하는 arr의 death를 1로 바꾸고, map에서 index를 제거

- 잡은 물고기의 크기를 dab에 더한다

3. tmp배열을 지역으로 선언한 후, arr에 담긴, 죽지 않은 물고기들을 하나씩 검사하며 이동시킨다

- 이때, 속도가 배열보다 클 수 있는데, 솔직히 말해서 for문을 속도 만큼 돌려도 될 것 같긴하지만 비효율 적임

- 그냥 좌표점을 가지고 노는 것이 더욱 효율적이므로 조금만 머리를 써서 좌표점을 가지고 노는 것을 추천

4. 이동시킨 물고기는 tmp배열에 먼저 저장을 하는데, 이때 겹치는 부분이 있다면, 덩치를 비교해서 어떤 물고기가 살아남을 것인지 정한다

- 죽는 물고기는 death를 1로 바꾼다

5. 이렇게 한 타임을 모두 구현해주었다면 tmp에 저장된 것을 그대로 map에 복사해주면 된다

너무나도 전형적인 시뮬레이션이라 특별한 기법이 있는거도 아님...

#include <iostream>
#define MAXSIZE 102
using namespace std;
struct FISH {
    int x, y, s, z, dir, death;
}arr[MAXSIZE*MAXSIZE];
int map[MAXSIZE][MAXSIZE];
int dx[] = { 0, 0, 0, 1, -1 };
int dy[] = { 0, -1, 1, 0, 0 };
int R, C, M, dab;
int main(void) {
    cin >> R >> C >> M;
    for (int i = 1; i <= M; i++) {
        cin >> arr[i].y >> arr[i].x >> arr[i].s >> arr[i].dir >> arr[i].z;
        arr[i].y -= 1; arr[i].x -= 1;
        map[arr[i].y][arr[i].x] = i;
    }
    for (int t = 0; t < C; t++) {
        for (int y = 0; y < R; y++) { // 물고기 잡기
            if (map[y][t]) {
                arr[map[y][t]].death = 1;
                dab += arr[map[y][t]].z;
                map[y][t] = 0;
                break;
            }
        }
        int tmp[MAXSIZE][MAXSIZE] = { 0 };
        for (int i = 1; i <= M; i++) {
            if (arr[i].death) continue; // 죽은 물고기 continue;
            int ix = arr[i].x, iy = arr[i].y, s = arr[i].s, idir = arr[i].dir;
            int nx, ny;
            while (1) {
                nx = ix + s * dx[idir]; ny = iy + s * dy[idir];
                if (nx < C && ny < R && ny >= 0 && nx >= 0)
                    break;
                if (idir == 1 && ny < 0) { s -= iy; iy = 0; idir = 2;  }
                else if (idir == 2 && ny >= R) { s -= R - 1 - iy; iy = R - 1; idir = 1;   }
                else if (idir == 3 && nx >= C) { s -= C - 1 - ix; ix = C - 1; idir = 4; }
                else if (idir == 4 && nx < 0) { s -= ix; ix = 0; idir = 3;  }
            }
            if (tmp[ny][nx]) {
                if (arr[tmp[ny][nx]].z < arr[i].z) { arr[tmp[ny][nx]].death = 1; tmp[ny][nx] = i; }
                else arr[i].death = 1;
            }
            else tmp[ny][nx] = i;
            arr[i].x = nx; arr[i].y = ny; arr[i].dir = idir;
            
        }
        for (int y = 0; y < R; y++)
            for (int x = 0; x < C; x++)
                map[y][x] = tmp[y][x];
    }
    cout << dab << endl;
    return 0;
}