Life Engineering
[BOJ 21608] 상어 초등학교 (C++) 본문
https://www.acmicpc.net/problem/21608
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int classroom[21][21] = { 0, };
struct info {
int like, vacant, row, col;
bool operator<(const info &b) const {
if (like == b.like) {
if (vacant == b.vacant) {
if (row == b.row) {
return col > b.col; //열 오름차순으로
}
return row > b.row; //행 오름차순으로
}
return vacant < b.vacant;
}
return like < b.like; //like 내림차순으로
}
};
int main() {
int N, num, x;
int ans = 0;
vector<int> order;
map<int, vector<int> > m;
cin >> N;
for (int i = 0; i < N * N; i++) {
cin >> num;
order.push_back(num);
for (int j = 0; j < 4; j++) {
cin >> x;
m[num].push_back(x);
}
}
for (int student : order) {
priority_queue<info> q;
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (classroom[r][c] != 0)
continue;
int l = 0; int v = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dx[d];
int nc = c + dy[d];
if (nr >= 1 && nr <= N && nc >= 1 && nc <= N) {
if (classroom[nr][nc] == 0)
v++;
else {
if (find(m[student].begin(), m[student].end(), classroom[nr][nc]) != m[student].end())
l++;
}
}
}
q.push({ l,v,r,c });
}
}
info i = q.top();
classroom[i.row][i.col] = student;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int student = classroom[i][j];
int cnt = 0;
for (int k = 0; k < 4; k++) {
int nr = i + dx[k];
int nc = j + dy[k];
if (nr >= 1 && nr <= N && nc >= 1 && nc <= N) {
if (find(m[student].begin(), m[student].end(), classroom[nr][nc]) != m[student].end()) {
cnt++;
}
}
}
switch (cnt) {
case 0:
break;
case 1:
ans += 1;
break;
case 2:
ans += 10;
break;
case 3:
ans += 100;
break;
case 4:
ans += 1000;
break;
}
}
}
cout << ans << "\n";
return 0;
}
구현 문제.
우선순위 큐를 이용해서, 조건을 만족하는 것이 제일 front에 나오도록 했다.
(like 내림차순->vacant 내림차순->행 오름차순->열 오름차순)
탐색은 N*N의 자리를 돌면서(이때 자리가 정해진 좌표는 탐색하지 않는다), 주변 4방향의 상태를 체크한 후(빈칸인지, 좋아하는 학생 수), 우선순위 큐에 {좋아하는 학생 수, 빈칸, 행, 열} 을 넣어준다. (행,열)의 인접에 좋아하는 학생 수와 빈칸이 몇개 있는지 기록하는 것이다. N*N개 탐색이 끝나면, 큐의 제일 맨 앞쪽에 있는 것이 적정 좌석이다.
그곳에 해당 student를 배정해주면 된다.
struct를 만들어서 like, vacant, row, col 을 멤버로 두었다. 해당 (row, col) 좌표 인접에 like가 몇개인지 vacant 가 몇개인지 나타내는 것이다. 비교 연산자를 오버로딩해서, priority_queue를 쓸 때 조건에 맞게 정렬이 가능하도록 했다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 위장 (Python3) (0) | 2021.10.21 |
---|---|
[BOJ 19236] 청소년 상어 (C++) (0) | 2021.10.20 |
[BOJ 17779] 게리맨더링 2 (C++) (0) | 2021.10.18 |
[프로그래머스] 여행경로 (Python3) (0) | 2021.10.17 |
[프로그래머스] 전력망을 둘로 나누기 (Python3) (0) | 2021.10.17 |