반응형
문제 링크: https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
<문제 풀이> 우선순위큐, 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++소스코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
#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;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 17626번] Four Squares (0) | 2023.04.12 |
|---|---|
| [백준 23291번] 어항 정리 (0) | 2023.04.08 |
| [백준 23289번] 온풍기 안녕! (0) | 2023.04.06 |
| [백준 1938번] 통나무 옮기기 (0) | 2023.04.04 |
| [백준 9944번] NxM 보드 완주하기 (0) | 2023.04.01 |
