문제
https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
설명
4방향을 계속해서 체크해주면 되는 문제이며 아무 생각 없이 BFS를 떠올리지 말자
또한 여러 우선순위 조건이 있을 때는 Priority_queue를 쓰는 것도 좋은 방법인 것 같다.
마지막으로 for문 여러 개 중첩 시 순서를 잘 설계하고 코드 구현에 들어가자!! (+배열 인덱스 주의)
코드
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N;
int map[21][21];
bool visited[21][21];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
struct Student {
int num;
int arr[4];
};
Student human[2000];
struct ABC {
int blank;
int like_num;
int r;
int c;
};
struct cmp {
bool operator()(ABC a,ABC b) {
//1,2,3 각각 우선순위 배정
if (a.like_num == b.like_num) {
if (a.blank == b.blank) {
if (a.r == b.r) {
return a.c > b.c;
}
return a.r > b.r;
}
return a.blank < b.blank;
}
return a.like_num < b.like_num;
}
};
priority_queue<ABC, vector<ABC>, cmp> pq;
void findSit(int y,int x,int k) {
int like_cnt = 0;
int blank_cnt = 0;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
for (int j = 0; j < 4; j++) {
if (map[ny][nx] == human[k].arr[j]) {
like_cnt++;
}
}
if (map[ny][nx] == 0) {
blank_cnt++;
}
}
pq.push({ blank_cnt,like_cnt,y,x });
}
int main() {
cin >> N;
for (int i = 0; i < N * N; i++) {
cin >> human[i].num;
for (int j = 0; j < 4; j++) {
cin >> human[i].arr[j];
}
}
for (int i = 0; i < N * N; i++) {
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (map[y][x] == 0) {
findSit(y, x,i);
}
}
}
map[pq.top().r][pq.top().c] = human[i].num; //자리배정완료
//pq초기화 까먹지말자
while (!pq.empty()) {
pq.pop();
}
}
//만족도조사
int answer = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
int score = 0;
for (int i = 0; i < N * N; i++) {
if (map[y][x] == human[i].num) {
for (int j = 0; j < 4; j++) {
int ny = y + dy[j];
int nx = x + dx[j];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
for (int k = 0; k < 4; k++) {
if (map[ny][nx] == human[i].arr[k]) {
score++;
}
}
}
}
}
if (score == 1) answer += 1;
if (score == 2) answer += 10;
if (score == 3) answer += 100;
if (score == 4) answer += 1000;
}
}
cout << answer;
return 0;
}'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] 파티 (1238/C++) (0) | 2023.09.30 |
|---|---|
| [백준] 통계학 (2108/C++) (0) | 2022.02.02 |
| [백준] 나는야 포켓몬 마스터 이다솜 (1620/C++) (0) | 2022.01.31 |
| [백준] 경로 찾기 (11403/C++) (0) | 2022.01.30 |
| [백준] 최대 힙 (11279/C++) (0) | 2022.01.26 |