[구현 알고리즘] 청소년 상어 / G3

기출 : 2020 삼성전자 공채

 

아이디어는 다음과 같다

 

1. 현재 상태 꺼내기

2. 물고기 이동

3. 먹을 수 있는 물고기를 향해 상어를 이동하고 상태 저장

4. 먹을 수 있는 물고기가 없다면 최댓값 갱신, 있다면 1번으로

 

각 단계별로 살펴보자

 

1. 현재 상태 꺼내기

 

현재 상태는 물고기들의 값, 방향이 저장된 배열과 상어의 값, 방향이 포함된다

상태를 저장하기 위해 큐를 사용했다

현재 상태를 꺼내 상어가 움직이는 경우를 각각 큐에 저장했다

 

2. 물고기 이동

 

물고기를 이동시키기 위해 물고기의 크기가 작은 순서대로 저장된 배열이 필요했다

우선순위 큐에 그 값을 넣는 것으로 처리했으나 나중에 확인한 결과 이 과정이 없어도 시간 복잡도에는 문제가 없다

물고기를 회전시키고 이동이 가능한 경우 swap하는 방식으로 처리했다

void moveFish(vector<vector<fish>>& f) {
    priority_queue<int,vector<int>, greater<int>> pq;
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j < 4;j++) {
            pq.push(f[i][j].val);
        }
    }
    while (!pq.empty()) {
        int curval = pq.top(); pq.pop();
        if (curval > 0) {
            int curx;
            int cury;
            for (int i = 0;i < 4;i++) {
                for (int j = 0;j < 4;j++) {
                    if (f[i][j].val == curval) {
                        curx = i; cury = j;
                        break;
                    }
                }
            }
            for (int i = 0;i < 8;i++) {
                int mdir = (f[curx][cury].dir + i) % 8;
                int mx = curx + dx[mdir];
                int my = cury + dy[mdir];
                if (mx < 0 || my < 0 || mx >= 4 || my >= 4) continue;
                if (f[mx][my].val == -1) continue;
                f[curx][cury].dir = mdir;
                swap(f[mx][my], f[curx][cury]);
                break;
            }
        }
    }
}

 

3. 먹을 수 있는 물고기를 향해 상어를 이동하고 상태 저장

 

상어를 이동시키면 상태가 모두 갱신되었으므로 큐에 저장한다

vector<vector<fish>> moveShark(state cur, int x, int y) {
    cur.v[cur.sx][cur.sy].val = 0;
    cur.v[x][y].val = -1;
    return cur.v;
}

 

4. 먹을 수 있는 물고기가 없다면 최댓값 갱신, 있다면 1번으로

 

상어의 종료 조건이므로 이를 적용했다

 

다음은 종합된 코드이다

#include<bits/stdc++.h>
using namespace std;

// 구조체 fish
struct fish {
    int val;
    int dir;
    fish(int v, int d) : val(v), dir(d) {};
};

// 넘길 state
struct state {
    vector<vector<fish>> v;
    fish shark;
    int sx;
    int sy;
    state(vector<vector<fish>> fv, fish s, int x, int y) : v(fv), shark(s), sx(x), sy(y) {};
};

// 윗 방향부터 45도 반시계 순서
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,-1,-1,-1,0,1,1,1};

// fish 배열
vector<vector<fish>> fv;

// state 큐
queue<state> sq;

void printboard(vector<vector<fish>> f) {
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j < 4;j++) {
            cout << f[i][j].val << " ";
        }
        cout << "\n";
    }
    cout << "\n";
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j < 4;j++) {
            cout << f[i][j].dir << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void moveFish(vector<vector<fish>>& f) {
    priority_queue<int,vector<int>, greater<int>> pq;
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j < 4;j++) {
            pq.push(f[i][j].val);
        }
    }
    while (!pq.empty()) {
        int curval = pq.top(); pq.pop();
        if (curval > 0) {
            int curx;
            int cury;
            for (int i = 0;i < 4;i++) {
                for (int j = 0;j < 4;j++) {
                    if (f[i][j].val == curval) {
                        curx = i; cury = j;
                        break;
                    }
                }
            }
            for (int i = 0;i < 8;i++) {
                int mdir = (f[curx][cury].dir + i) % 8;
                int mx = curx + dx[mdir];
                int my = cury + dy[mdir];
                if (mx < 0 || my < 0 || mx >= 4 || my >= 4) continue;
                if (f[mx][my].val == -1) continue;
                f[curx][cury].dir = mdir;
                swap(f[mx][my], f[curx][cury]);
                break;
            }
        }
    }
}

vector<vector<fish>> moveShark(state cur, int x, int y) {
    cur.v[cur.sx][cur.sy].val = 0;
    cur.v[x][y].val = -1;
    return cur.v;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int maxval = 0;

    int sdir;   // 상어 초기 방향
    int sval;   // 상어 초기값
    int sx;
    int sy;

    // 초기상태 입력
    for (int i = 0;i < 4;i++) {
        vector<fish> v;
        for (int j = 0;j < 4;j++) {
            int val, dir;
            cin >> val >> dir;
            if (i == 0 && j == 0) {
                sdir = dir;
                sval = val;
                sx = i;
                sy = j;
                fish f(-1, dir - 1);
                v.push_back(f);
                continue;
            }
            fish f(val, dir - 1);
            v.push_back(f);
        }
        fv.push_back(v);
    }

    fish shark(sval, sdir-1);
    state s(fv,shark,sx, sy);
    sq.push(s); 
    while (!sq.empty()) {
        state cur = sq.front(); sq.pop();
        moveFish(cur.v);
        int x = cur.sx;
        int y = cur.sy;
        x += dx[cur.shark.dir];
        y += dy[cur.shark.dir];
        bool done = false;
        while (x >= 0 && y >= 0 && x < 4 && y < 4) {
            if (cur.v[x][y].val > 0) {
                fish nextshark(cur.shark.val + cur.v[x][y].val, cur.v[x][y].dir );
                vector<vector<fish>> nextfish = moveShark(cur, x, y);
                state nextstate(nextfish,nextshark,x,y);
                sq.push(nextstate);
                done = true;        
            }
            x += dx[cur.shark.dir];
            y += dy[cur.shark.dir];
        }
        if (!done) {
            maxval = max(maxval, cur.shark.val);
        }
    }
    cout << maxval;
    return 0;
}