[백준] 상어 초등학교 21608번 (c++) 구현, 우선순위 큐 정렬

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

풀이 방법

호흡이 길 뿐 어려운 문제는 아니다 순서대로 하나씩 배열한 후 점수를 구하면 된다.

다음 좌석을 구하기 위해 선호하는 학생 수 , 빈자리 수, y가 작은, x가 작은으로 정렬을 하기 위해 모든 자리를 돌며 우선순위 큐를 사용해서 다음 자리를 선택했다.

 

주의 점

1. 기본적인 우선순위 큐는 MAX Heap이다
2. bool operator < (const Seat& a) const { 
   1. 위 함수는 작은 경우 true를 리턴해야 하므로 주의해야 한다. 
   2. 일반적인 sort에서 사용하려는 사용자 정의 cmp은 다름
3. 점수 계산시 모든 좌석을 배정 다 한 후 해야 한다.

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

int N, student_num, ans;
vector<vector<int > > likes;
vector<int> order;
int school[21][21];
int point[21][21];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

struct Seat {
    int y;
    int x;
    int like_cnt;
    int empty_cnt;

    Seat(int y, int x, int like_cnt, int empty_cnt) : x(x), y(y), like_cnt(like_cnt), empty_cnt(empty_cnt) {

    }

    bool operator < (const Seat& a) const { 
        if (like_cnt < a.like_cnt) return true; // like_cnt가 클수록 우선
        else if (like_cnt == a.like_cnt) {
            if (empty_cnt < a.empty_cnt) {
                return true; // empty_cnt가 클수록 우선
            }
            else if (empty_cnt == a.empty_cnt) {
                if (y > a.y) {
                    return true; // y가 작을수록 우선
                }
                else if (y == a.y) {
                    if (x > a.x) {
                        return true; // x가 작을수록 우선
                    }
                    else return false;
                }
            }
            else return false;
        }
        else return false;
    }
};

pair<int, int> count_like(int idx, int y, int x) { // 호감도 수, 빈 공간 수 계산
    int like_cnt = 0, empty_cnt = 0;
    for (int i =0;i < 4;i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if( ny < 1 || ny >= N+1 || nx < 1 || nx >= N+1) continue;
        int people = school[ny][nx];
        if (people == 0) empty_cnt++;
        for (int k = 0;k < 4;k++) { // 선호하는 사람인지 체크하는 함수
            if (people == likes[idx][k]) {             
                like_cnt++;
                continue;
            }
        }
    }    
    return make_pair(like_cnt, empty_cnt);
}

Seat find_seat(int idx) { // 다음 좌석
    priority_queue<Seat> s;
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            if (school[i][j] == 0) {  //빈 자리이면 후보에 추가              
                pair<int, int> p = count_like(idx, i, j);
                s.push(Seat(i, j, p.first, p.second));                
            }
        }
    }
    return s.top(); // 우선순위 큐를 사용해 정렬
}

void cal_point() {

    for (int i = 1;i < N+1;i++) {
        for (int j = 1;j < N+1;j++) {
            int idx = school[i][j];
            for(int k = 0;k < 4;k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny < 1 || ny > N || nx < 1 || nx > N) continue;
                int people = school[ny][nx], cnt = 0;
                for (int z = 0; z < 4; z++) {
                    if (people == likes[idx][z]) {
                        cnt++;
                        continue;
                    }
                }
                point[i][j] += cnt;
            }
        }
    }

    int total_point = 0;
    for (int i = 1;i < N+1;i++) {
        for (int j = 1;j < N+1;j++) {
            if (point[i][j] == 1) total_point += 1;
            else if (point[i][j] == 2) total_point += 10;
            else if (point[i][j] == 3) total_point += 100;
            else if (point[i][j] == 4)total_point += 1000;
        }
    }
    ans = total_point;
}
void sol() {    
    for (int i = 0;i < student_num;i++) {
        Seat s = find_seat(order[i]);        
        school[s.y][s.x] = order[i];                
    }
    
}
int main() {
    cin >> N;
    student_num = N*N;
    memset(school, 0, sizeof(school));
    memset(point, 0, sizeof(point));
    likes.resize(student_num+1);
    for (int i = 0;i < student_num;i++) {
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        order.push_back(a);
        likes[a].push_back(b);
        likes[a].push_back(c);
        likes[a].push_back(d);
        likes[a].push_back(e);
    }
    sol();
    cal_point();    
    cout << ans << endl;    
    return 0;
}