https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
코드 설명
지독한 구현 문제이다 삼성 문제는 구조체를 통해 담아두는 게 중요한 것 같다. 그리고 시간이 걸리더라도 설계를 최대한 상세하게 완벽하게 해 주는 것이 좋은 것 같다...(이번 문제 같은 경우 for문 속의 for문이 너무도 많기 때문에 작성하다가 놓친다)
우선순위 큐를 구현해서 문제에서 나온 우선순위대로 구현해준다.
map을 전체 탐색 하면서 0인 경우 들어가서 주변에 빈칸이 있는지++ , 좋아하는 친구가 있는지 ++ 체크해서 우선순위 큐에 넣어준다.
이후 마지막에 만족도 검사를 하면 된다
코드
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int map[501][501];
bool visited[501][501];
struct human {
int idx;
int like[4];
int y;
int x;
};
struct pp {
int y;
int x;
int blankcnt;
int friendcnt;
};
struct cmp {
bool operator()(pp a,pp b) {
if (a.friendcnt == b.friendcnt) {
if (a.blankcnt == b.blankcnt) {
if (a.y == b.y) {
return a.x > b.x;
}
return a.y > b.y;
}
return a.blankcnt < b.blankcnt;
}
return a.friendcnt < b.friendcnt;
}
};
int jumsu[5] = { 0,1,10,100,1000 };
int N;
vector<human> child;
int main() {
cin >> N;
for (int i = 0; i < N * N; i++) {
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
child.push_back({ a,{b,c,d,e},0,0 });
//놓일 자리 탐색
}
for (int i = 0; i < child.size(); i++) {
priority_queue<pp, vector<pp>, cmp> pq;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (map[y][x] == 0) {
int blank_cnt = 0;
int friend_cnt = 0;
for (int k = 0; k < 4; k++) {
int ny = y + dy[k];
int nx = x + dx[k];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (map[ny][nx] == 0) {
blank_cnt++;
}
else {
for(int j=0;j<4;j++){
if (map[ny][nx] == child[i].like[j]) {
friend_cnt++;
break;
}
}
}
}
pq.push({ y,x,blank_cnt,friend_cnt });
}
}
}
if (!pq.empty()) {
int dy = pq.top().y;
int dx = pq.top().x;
map[dy][dx] = child[i].idx;
child[i].y = dy;
child[i].x = dx;
}
}
//만족도 조사
int res = 0;
for (int i = 0; i < N * N; i++) {
int y = child[i].y;
int x = child[i].x;
int friends = 0;
for (int k = 0; k < 4; k++) {
int ny = y + dy[k];
int nx = x + dx[k];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
for (int j = 0; j < 4; j++) {
if (map[ny][nx] == child[i].like[j]) {
friends++;
break;
}
}
}
res += jumsu[friends];
}
cout << res;
return 0;
}'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] 탈출 (3055/C++) (0) | 2021.08.14 |
|---|---|
| [백준] 안전영역 (2468/C++) (0) | 2021.08.06 |
| [백준] 마법사 상어와 비바라기(21610 /C++) (0) | 2021.06.04 |
| [백준] 연구소 (14502번 / C++) (0) | 2021.06.01 |
| [백준] 단어 정렬 (1181/ C++) (0) | 2021.05.29 |