[C++] 삼성 SW 역량 테스트 기출문제 백준 21608번 상어 초등학교

 

 

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

21608번: 상어 초등학교

 

 

#include <bits/stdc++.h>
//[C++] 삼성 SW 역량 테스트 기출문제 백준

struct Info {
    int y, x;
    int blank;
    int like;
};

int n;
std::vector<std::unordered_set<int>> s;
std::vector<int> students;

int map[21][21];

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};


bool cmp (const Info & lhs, const Info & rhs){
    if (lhs.like == rhs.like){
        if (lhs.blank == rhs.blank){
            if (lhs.y == rhs.y) {
                return lhs.x < rhs.x;
            }
            return lhs.y < rhs.y;
        }
        return lhs.blank > rhs.blank;
    }
    return lhs.like > rhs.like;
}


void sit(int no) {
    std::vector<Info> candi;
    for (int y = 1; y <= n; ++y){
        for (int x = 1; x <= n; ++x){
            if (map[y][x] != 0) continue;       
            // 좋아하는 사람이 많고, 비어있는 칸이 많고, 행의 번호가 작고, 열의 번호가 작은 칸 선택
            int like = 0, blank = 0;
            for (int dir = 0; dir < 4; ++dir){
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (ny < 1 || ny > n || nx < 1 || nx > n) continue;
                if (map[ny][nx] == 0) ++blank;
                if (s[no].find(map[ny][nx]) != s[no].end()) ++like;
            }
            candi.push_back({y, x, blank, like});
        }
    }
    std::sort(candi.begin(), candi.end(), cmp);
    map[candi[0].y][candi[0].x] = no;
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;

    s.resize(n * n + 1);


    int no, other;
    for (int i = 1; i <= n * n; ++i){
        std::cin >> no;
        students.push_back(no);
        for (int j = 0; j < 4; ++j){
            std::cin >> other;
            s[no].insert(other);
        }
    }

    for (int student : students){
        sit(student);
    }

    int ret = 0;

    for (int y = 1; y <= n; ++y){
        for (int x = 1; x <= n; ++x){
            int no = map[y][x];
            int cnt = 0;
            for (int dir = 0; dir < 4; ++dir){
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (ny < 1 || ny > n || nx < 1 || nx > n) continue;
                if (s[no].find(map[ny][nx]) != s[no].end()) ++cnt;
            }
            switch (cnt){
                case 1:
                ret += 1;
                break;
                case 2:
                ret += 10;
                break;
                case 3:
                ret += 100;
                break;
                case 4:
                ret += 1000;
                break;
            }
        }
    }

    std::cout << ret << '\n';
    return 0;
}