[백준 21608번] 상어 초등학교

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

21608번: 상어 초등학교

<문제 풀이> 우선순위큐, SET, 구현

 

아래와 같이 SET을 사용하면 인접한 칸에 있는 학생들이 i번 학생이 좋아하는 학생인지를 쉽게 찾을 수 있습니다.

unordered_set<int> prefer[401]; //prefer[i] : i번 학생이 좋아하는 학생들의 번호

인접한 칸에 있는 학생이 좋아하는 학생인지 확인할 때 perfer[i]에 값이 존재하는지만 확인하면 됩니다.

 

 

아래와 같이 우선순위큐를 사용하면 학생들의 자리를 쉽게 배정할 수 있습니다.

 

struct cmp {
	bool operator()(const Position& a, const Position& b) {
		if (a.preferCnt == b.preferCnt) {
			if (a.blankCnt == b.blankCnt) {
				if (a.r == b.r) { //4. 3을 만족하는 칸도 여러 개 인경우 열의 번호가 가장 작은 칸으로 자리를 정한다.
					return a.c > b.c; 
				}
				else { // 3. 2를 만족하는 칸도 여러 개인 경우 행의 번호가 가장 작은 칸으로 자리를 정한다.
					return a.r > b.r;
				}
			}
			else { // 2. 1을 만족하는 칸이 여러 개이면, 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
				return a.blankCnt < b.blankCnt;
			}
		}
		else { // 1. 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
			return a.preferCnt < b.preferCnt; 
		}
	}
};


priority_queue<Position, vector<Position>, cmp> pq;

 

 

 

<전체 C++소스코드>

#include <iostream>
#include <unordered_set>
#include <queue>
#include <vector>
using namespace std;
 
int n;
int board[21][21];
unordered_set<int> prefer[401]; //prefer[i] : i번 학생이 좋아하는 학생들의 번호
vector<int> students;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
const int satisfaction[5] = { 0, 1, 10, 100, 1000 };
 
class Position {
public:
    int preferCnt;
    int blankCnt;
    int r, c;
    Position(int preferCnt, int blankCnt, int r, int c) {
        this->preferCnt = preferCnt;
        this->blankCnt = blankCnt;
        this->r = r;
        this->c = c;
    }
};
 
struct cmp {
    bool operator()(const Position& a, const Position& b) {
        if (a.preferCnt == b.preferCnt) {
            if (a.blankCnt == b.blankCnt) {
                if (a.r == b.r) { //4. 3을 만족하는 칸도 여러 개 인경우 열의 번호가 가장 작은 칸으로 자리를 정한다.
                    return a.c > b.c; 
                }
                else { // 3. 2를 만족하는 칸도 여러 개인 경우 행의 번호가 가장 작은 칸으로 자리를 정한다.
                    return a.r > b.r;
                }
            }
            else { // 2. 1을 만족하는 칸이 여러 개이면, 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
                return a.blankCnt < b.blankCnt;
            }
        }
        else { // 1. 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
            return a.preferCnt < b.preferCnt; 
        }
    }
};
 
void input() {
    cin >> n;
    for (int i = 1; i <= n * n; i++) {
        int p, a, b, c, d;
        cin >> p >> a >> b >> c >> d;
        prefer[p].insert(a);
        prefer[p].insert(b);
        prefer[p].insert(c);
        prefer[p].insert(d);
        students.push_back(p);
    }
}
 
 
void select() {
    for(auto student : students){ // 학생을 한 명씩 배치한다.
        priority_queue<Position, vector<Position>, cmp> pq;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (board[i][j]) continue;
                int preferCnt = 0;
                int blankCnt = 0;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
                    if (board[nx][ny] == 0) blankCnt++;
                    else if (prefer[student].find(board[nx][ny]) != prefer[student].end()) preferCnt++; // 인접한 칸 중에서 종아하는 학생들의 수
                }
                pq.push({ preferCnt, blankCnt, i, j });
            }
        }
        if (!pq.empty()) {
            auto target = pq.top(); // 우선순위 큐의 top에 있는 좌표가 학생의 자리
            board[target.r][target.c] = student;
        }
    }
}
 
 
int getTotalSatisfaction() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int preferCnt = 0;
            int student = board[i][j];
            for (int dir = 0; dir < 4; dir++) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
                if (prefer[student].find(board[nx][ny]) != prefer[student].end()) preferCnt++;
            }
            ans += satisfaction[preferCnt];
 
        }
    }
    return ans;
}
 
 
void solve() {
    input();
    select();
    cout << getTotalSatisfaction();
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    solve();
    
 
    return 0;
}