[백준 21608] 상어 초등학교 (C++)

문제 링크: https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

1. 주의할 점

- 우선순위 큐 정렬을 잘 정리한다

- 요구에 맞게 정확히 구현한다

 

2. 구현

- Arr[][] 배열을 통해 해당 자리에 위치한 학생 번호를 저장한다

- favorPeople[] Set을 통해 해당 학생이 선호하는 학생 번호를 저장한다

- score[] 배열을 통해 선호하는 학생들의 수에 해당하는 점수를 반환한다

- 배치할 학생들의 순서를 people 큐에 저장하며 1개씩 뺀다

- Queue에서 뽑은 학생번호에 대해 Arr[][] 배열의 빈칸과 모두 비교한다

- findFav() 함수를 통해 해당 위치에 놓인다면 몇 명의 선호하는 학생과 인접해 있는지 반환한다

- findSpace() 함수를 통해 해당 위치에 학생이 놓인다면 몇 개의 빈 공간과 인접해 있는지 반환한다

- Arr[][] 배열에 모든 학생들이 위치했다면, Cal() 함수를 통해 각 학생들의 만족도를 Answer에 더하고 Answer를 최종적으로 반환하여 총 만족도를 출력한다

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int y,x,favorCnt,spaceCnt;
};
struct cmp{
    bool operator()(info &a, info &b){
        if(a.favorCnt==b.favorCnt){
            if(a.spaceCnt==b.spaceCnt){
                if(a.y==b.y){
                    return a.x > b.x;
                }
                return a.y > b.y;
            }
            return a.spaceCnt < b.spaceCnt;
        }
        return a.favorCnt < b.favorCnt;
    }
};
int num;
int arr[20][20];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
set<int> favorPeople[401];		//선호하는 학생번호를 담는다
int score[5]={0,1,10,100,1000};

int findFav(int y, int x, int cidx){
    int cnt=0;
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx>=0 && ny>=0 && nx<num && ny<num &&favorPeople[cidx].find(arr[ny][nx])!=favorPeople[cidx].end())
            cnt++;
    }
    return cnt;
}

int findSpace(int y, int x){
    int cnt=0;
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx>=0 && ny>=0 && nx<num && ny<num && arr[ny][nx]==0)
            cnt++;
    }
    return cnt;
}

int cal(){
    int answer = 0;
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            answer += score[findFav(i,j,arr[i][j])];
    return answer;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>num;
    int idx,a;
    queue<int> people;      //넣는 학생 순서
    for(int i=0;i<num*num;i++){
        cin>>idx;
        for(int j=0;j<4;j++){
            cin>>a;
            favorPeople[idx].insert(a);
        }
        people.push(idx);
    }
    while(!people.empty()){
        int cidx = people.front();
        people.pop();
        priority_queue<info,vector<info>,cmp> pq;       //자리에 대한 정보 담는다
        for(int i=0;i<num;i++){
            for(int j=0;j<num;j++){
                int val = arr[i][j];
                if(val>0) continue;     //이미 학생이 있는 경우
                pq.push({i,j,findFav(i,j,cidx),findSpace(i,j)});
            }
        }
        arr[pq.top().y][pq.top().x]=cidx;
    }
    cout << cal();
    return 0;
}