[21608] 상어 초등학교

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

21608번: 상어 초등학교

<문제>

그냥 잘 구현하면 되는 문제라 별로 적을게 없다..

 

모든 (y, x)에 대해 (인접한 칸에 좋아하는 학생 수)를 구해야 하는데, 현재 (i, j)에서의 값을 cnt에 넣었고

현재 시점까지의 최대 cnt를 curScore에 저장해두었다고 생각해보면,

cnt<curScore인 경우에는 무시하고,

cnt==curScore인 경우에는 현재 위치를 후보지에 추가하고,

cnt>curScore인 경우에는 기존 모든 후보지를 clear()해주고 현재 위치를 추가하면 된다.

위 3가지 경우를 잘 나누어 주는게 이 문제에서 가장 어려울 법 한 구현요소이다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
int n, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}, a[21][21];
vector<int> in[403];
int getEmptyScore(int sy, int sx) {
    int i, ret = 0;
    for (i = 0; i < 4; i++) {
        int y = sy + dy[i];
        int x = sx + dx[i];
        if (y < 0 || x < 0 || y >= n || x >= n) continue;
        ret += (a[y][x] == 0);
    }
    return ret;
}
void f(vector<int> chk, int num) {
    int i, j, k, curScore = -1;
    vector<pi> pos;  //배치 후보지
    pos.clear();
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (a[i][j] != 0) continue;
            int cnt = 0;
            for (k = 0; k < 4; k++) {
                int y = i + dy[k];
                int x = j + dx[k];
                if (y < 0 || x < 0 || y >= n || x >= n || a[y][x] == 0)
                    continue;
                if (find(chk.begin(), chk.end(), a[y][x]) != chk.end()) cnt++;
            }
            if (curScore < cnt) {  //[1]
                curScore = cnt;
                pos.clear();
                pos.push_back({i, j});
            } else if (curScore == cnt) {
                pos.push_back({i, j});
            }
        }
    }
    int maxEmptyScore = 0;
    vector<int> score;
    for (i = 0; i < pos.size(); i++) {
        int cy = pos[i].first, cx = pos[i].second;
        int curEmptyScore = getEmptyScore(cy, cx);
        score.push_back(curEmptyScore);
        maxEmptyScore = max(curEmptyScore, maxEmptyScore);
    }
    vector<pi> temp;
    for (i = 0; i < score.size(); i++) {
        if (score[i] == maxEmptyScore) {
            temp.push_back(pos[i]);
        }
    }
    pos = temp;  //[2]
    sort(pos.begin(), pos.end(), [](pi a, pi b) -> bool {
        if (a.first == b.first) return a.second < b.second;
        return a.first < b.first;
    });  //[3]
    a[pos.front().first][pos.front().second] = num;
    return;
}
int getTotalScore(void) {
    int i, j, k, ret = 0;
    int baseScore[5] = {0, 1, 10, 100, 1000};
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            int cnt = 0;
            int curNum = a[i][j];
            for (k = 0; k < 4; k++) {
                int y = i + dy[k];
                int x = j + dx[k];
                if (y < 0 || x < 0 || y >= n || x >= n) continue;
                if (find(in[curNum].begin(), in[curNum].end(), a[y][x]) !=
                    in[curNum].end()) {
                    cnt++;
                }
            }
            ret += baseScore[cnt];
        }
    }
    return ret;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int i, j, S = n * n;
    for (i = 0; i < S; i++) {
        int num;
        cin >> num;
        vector<int> chk;
        chk.resize(4);
        for (j = 0; j < 4; j++) {
            cin >> chk[j];
            in[num].push_back(chk[j]);
        }
        f(chk, num);
    }
    int ans = getTotalScore();
    cout << ans;
    return 0;
}