[BOJ 19236] 청소년 상어

 

문제 링크

https://www.acmicpc.net/contest/problem/19236

B번: 청소년 상어

데이터 검증을 위해 "대회 - 연습" 에 새로 올라온 문제인데,

아마도 유형이나 시기를 보면 이번 2020년 상반기 삼성 코테 기출인듯 하다.

---

아이디어

 

시뮬레이션으로 주어진 순서에 따라 구현하자.

 

1. 상어는 (0,0)에 들어가 그 칸의 물고기를 잡아 먹고 그 물고기의 방향을 얻는다.

 

2. 1번 물고기부터 16번 물고기까지 살아 있다면, 문제에 주어진대로 이동한다.
   2-1. 물고기가 바라보는 칸이 상어거나 경계를 넘어가면 continue
   2-2. (이제 빈 칸이거나 다른 물고기가 있는 칸이다.) 해당 칸으로 이동하여
        map의 정보와 물고기들의 위치, 방향 정보를 갱신한다.

 

3. 상어가 바라보는 방향의 칸에 물고기가 있다면, 해당 칸으로 즉시 이동해 물고기 중 아무거나 한 마리를 잡아 먹는다.

   이 때, 잡아먹을 물고기가 없다면 지금까지 잡아먹은 물고기 번호의 합을 비교하고 종료.

 

- map[i][j]  : 현재 (i, j)에 존재하는 물고기의 번호

- dead[i]    : i번째 물고기가 죽었다면 true

- vector<fish>fishes[i] : i번째 물고기의 (y,x)값과 방향을 저장

- 상어의 번호는 17로 정해주었다

 

- simulation (int sy, int sx, int sd, int cnt, int state[][], bool death[], vector <fish>f )

- sy, sx  : 현재 상어의 위치

- sd       : 현재 상어의 방향

- cnt     : 지금까지 먹은 물고기 번호의 합 

- state  : 현재 공간의 상태

- death : 현재 물고기들의 생존여부

-  f         : 현재 물고기들의 위치와 방향정보

---

주의할 점

 

상어가 (0,0)에서 오른쪽 아래 방향을 바라본다고 하고 (1,1), (2,2), (3,3) 모두 물고기가 있다고 생각해보자.

상어가 (1,1)의 물고기를 먹거나 (2,2)의 물고기를 먹거나 (3,3)의 물고기를 먹을 수 있다.

따라서 (1,1)의 물고기를 먹고 갱신한 state, death, f를 그대로 (2,2)의 물고기를 먹는 simulation에 사용하면 안된다.

(2,2)를 잡아 먹는 것은 (1,1)을 잡아 먹지 않은 상태의 정보를 사용해야 한다.

마찬가지로 (3,3)을 잡아 먹는 것은 (1,1)도, (2,2)도 잡아 먹지 않은 상태의 정보를 사용해야 한다.

 

이를 위해서 simulation 함수에서 해당 정보(state, death, f)를 인자로 받아야하며

인자로 받은 state, death, f의 정보를 state2, death2, f2에 복사해 두었다가

상어가 다른 물고기를 잡아먹을 때 마다 이전 값으로 갱신해주는 것이 필요하다.

 

 

---

소스코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct fish {
    int y, x, d;
} fish;

const int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dx[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
vector <fish> fishes;
int a, b, map[5][5], sd, ans;
bool dead[20];

void simulate(int sy, int sx, int sd, int cnt, int state[5][5], bool death[20], vector<fish> f)
{

    //2. 물고기 이동
    for (int fish = 1; fish <= 16; ++fish) {
        if (death[fish]) continue;

        int fy = f[fish].y;
        int fx = f[fish].x;
        int fd = f[fish].d;
        for (int k = 0; k < 8; ++k) {
            int nd = (fd + k) % 8;
            int ny = fy + dy[nd];
            int nx = fx + dx[nd];
            if (ny < 0 || nx < 0 || ny > 3 || nx > 3)
                continue;

            int adj_fish = state[ny][nx];
            if (adj_fish == 17) continue;
            if (adj_fish == 0) {
                f[fish] = { ny, nx, nd };
                state[fy][fx] = 0;
                state[ny][nx] = fish;
                break;
            }
            else {
                f[fish].d = nd;
                swap(f[fish].y, f[adj_fish].y);
                swap(f[fish].x, f[adj_fish].x);
                swap(state[fy][fx], state[ny][nx]);
                break;
            }
        }
    }

    //3. 상어 이동
    bool fin = true;
    int nsy = sy + dy[sd], nsx = sx + dx[sd];
    while (nsy >= 0 && nsx >= 0 && nsy <= 3 && nsx <= 3) {

        int state2[5][5];
        bool death2[20];
        
        vector <fish> f2 = f;
        memcpy(state2, state, sizeof(state2));
        memcpy(death2, death, sizeof(death2));
        
        if (state2[nsy][nsx] > 0) {
            int fish_num = state2[nsy][nsx];
            death2[fish_num] = true;
            state2[sy][sx] = 0;
            state2[nsy][nsx] = 17;
            simulate(nsy, nsx, f[fish_num].d, cnt + fish_num, state2, death2, f2);
            fin = false;
        }
        nsy += dy[sd];
        nsx += dx[sd];
    }
    if (fin) {
        ans = max(ans, cnt);
        return;
    }
    return;
}

int main()
{
    fishes.resize(17);
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            scanf("%d %d", &a, &b);
            map[i][j] = a;
            fishes[a] = { i, j, b - 1 };
        }
    }

    //1. 상어 입장
    int init_fish = map[0][0];
    sd = fishes[init_fish].d;
    dead[init_fish] = true;
    map[0][0] = 17;

    simulate(0, 0, sd, init_fish, map, dead, fishes);
    printf("%d\n", ans);
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 언제나 부드럽게 알려주세요.