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

//21608 상어 초등학교
#include <vector>
#include <iostream>
#include <set>

using namespace std;
int n;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

void find_seat(vector<vector<int>> &seat, vector<set<int>> &like, int student){
    int min_val = 0;
    for(int i = 0 ; i < n ;i++){
        for(int j = 0 ; j < n ; j++){

            //이미 배정된 자리면 넘김
            if(seat[i][j]>0)
                continue;

            //배정되지 않은 자리
            int count = 0;
            int no_seat = 0;
            for(int k = 0 ; k < 4 ; k++){
                int nr = i+dr[k];
                int nc = j+dc[k];
                if(nr < 0 || nr >= n || nc < 0 || nc >= n)
                    continue;

                if(seat[nr][nc]<=0){ //아무도 안 앉아있음
                    no_seat++;
                    continue;
                }

                if(like[student].find(seat[nr][nc]) != like[student].end()){
                    count++;
                };
            }
            // 좋아하는 학생
            switch(count){
                case 0:
                    seat[i][j] = 0;
                    break;
                case 1:
                    seat[i][j] = -10;
                    min_val = min(min_val, seat[i][j]);
                    break;
                case 2:
                    seat[i][j] = -100;
                    min_val = min(min_val, seat[i][j]);
                    break;
                case 3:
                    seat[i][j] = -1000;
                    min_val = min(min_val, seat[i][j]);
                    break;
                case 4:
                    seat[i][j] = -10000;
                    min_val = min(min_val, seat[i][j]);
                    break;
            }
            // 비어있는 칸
            switch(no_seat){
                case 0:
                    seat[i][j] -= 0;
                    break;
                case 1:
                    seat[i][j] -= 1;
                    min_val = min(min_val, seat[i][j]);
                    break;
                case 2:
                    seat[i][j] -= 2;
                    min_val = min(min_val, seat[i][j]);
                    break;
                case 3:
                    seat[i][j] -= 3;
                    min_val = min(min_val, seat[i][j]);
                    break;
                case 4:
                    seat[i][j] -= 4;
                    min_val = min(min_val, seat[i][j]);
                    break;
            }
        }
    }

    for(int i = 0 ; i < n ;i++) {
        for (int j = 0; j < n; j++) {
            if(seat[i][j]==min_val){
                seat[i][j] = student;
                return;
            }
        }
    }
}

int print_answer(vector<vector<int>> &seat, vector<set<int>> &like){
    int sum = 0;
    for(int i = 0 ; i < n ;i++){
        for(int j = 0 ; j < n ; j++){
            int student = seat[i][j];
            int count = 0;
            for(int k = 0 ; k < 4 ; k++){
                int nr = i+dr[k];
                int nc = j+dc[k];
                if(nr < 0 || nr >= n || nc < 0 || nc >= n)
                    continue;
                if(like[student].find(seat[nr][nc]) != like[student].end()){
                    count++;
                };
            }
            switch(count){
                case 0:
                    sum += 0;
                    break;
                case 1:
                    sum += 1;
                    break;
                case 2:
                    sum += 10;
                    break;
                case 3:
                    sum += 100;
                    break;
                case 4:
                    sum += 1000;
                    break;
            }
        }
    }
    return sum;
}
int main() {
    cin >> n;
    int loop = n*n;
    vector<set<int>> like(n*n+1);
    vector<int> list;
    vector<vector<int>> seat(n, vector<int>(n, 0));
    while(loop--){
        int student;
        cin >> student;
        list.push_back(student);
        for(int i = 0 ; i < 4 ; i++){
            int l_student;
            cin >> l_student;
            like[student].insert(l_student);
        }
    }
    for(int i = 0 ; i < list.size() ; i++){
        find_seat(seat, like, list[i]);
    }

    //만족도 총 합 출력
    int answer = print_answer(seat, like);
    cout << answer;

    return 0;
}

 

코드가 이렇게 긴 걸 보니 더 좋은 코드가 많을 것 같다 ㅠㅠ

문제를 읽고 일단 만족도 합을 세는 코드부터 짜고(이쪽이 쉬우니까) 자리배정 코드를 짜는 게 좋을 것 같았다.

 

각 학생의 순서마다 모든 좌석을 검사해서 조건에 따라 점수를 기록하고, 점수가 가장 높은 좌석에 배치했다.

이차원 벡터는 하나만 쓰기위해 점수는 음수로 반전해서 기록했다.

 

자리배정 규칙은

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

인데, 3번의 경우 어차피 for문으로 첫 좌석부터 돌다 보면 자연히 만족하지 않겠나 싶었고

1번 조건에 더 높은 점수(-10, -100, -1000, -10000)를, 2번 조건에 더 낮은 점수(-1, -2, -3, -4)를 부여하는 것으로 차등 부여했다.