슈뢰딩거의 고등어
21608 상어초등학교 본문
https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
실버 1
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int dy[4] = {-1, 0, 0, 1};
const int dx[4] = {0, -1, 1, 0};
struct Student {
int no;
int y, x;
int friends[4];
};
int n, answer;
int arr[21][21];
vector <Student> st;
// 구현
// return how many close friend in y, x
int count_friend(int std_no, int y, int x) {
int result = 0;
for(int i=0; i<4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= n)
continue;
if (arr[ny][nx] == -1)
continue;
for(int f=0; f<4; f++) {
int friend_no = arr[ny][nx];
if (friend_no == st[std_no].friends[f]) {
result++;
}
}
}
return result;
}
// return how many blank near y, x
int count_blank(int y, int x) {
int result = 0;
for(int i=0; i<4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= n)
continue;
if(arr[ny][nx] == -1)
result++;
}
return result;
}
bool compare (pair<int, int> a, pair<int, int> b) {
if(a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
void solve() {
// init
memset(arr, -1, sizeof(arr));
for(int s=0; s<st.size(); s++) {
int student_no = st[s].no;
int tmp_arr[n][n];
// copy 때려주기
for(int i=0; i<n; i++)
for(int j=0; j<n; j++){
tmp_arr[i][j] = arr[i][j];
}
// check map
int max_f_value = -1;
vector <pair<int, int>> v;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
// if not empty skip!
if(tmp_arr[i][j] != -1)
continue;
// case1 > 친구인접 최대 위치 max_y, max_x
tmp_arr[i][j] = count_friend(s, i, j);
if(tmp_arr[i][j] > max_f_value) {
v.clear(); // 초기화
v.push_back(make_pair(i, j));
max_f_value = tmp_arr[i][j];
}
else if(tmp_arr[i][j] == max_f_value) {
v.push_back(make_pair(i, j));
}
}
// case 1
if (v.size() == 1) {
arr[v[0].first][v[0].second] = student_no;
st[s].y = v[0].first;
st[s].x = v[0].second;
continue;
}
int v_size = v.size();
int max_blank = -1;
vector <pair<int, int>> b;
// 인접빈칸개수
for(int i=0; i<v.size(); i++) {
int cy = v[i].first;
int cx = v[i].second;
int tmp_blank = count_blank(cy, cx);
if(tmp_blank > max_blank) {
max_blank = tmp_blank;
b.clear();
b.push_back(make_pair(cy, cx));
}
else if(tmp_blank == max_blank) {
b.push_back(make_pair(cy, cx));
}
}
// case 2
if(b.size() == 1) {
arr[b[0].first][b[0].second] = student_no;
st[s].y = b[0].first;
st[s].x = b[0].second;
continue;
}
sort(b.begin(), b.end(), compare);
// case 3
arr[b[0].first][b[0].second] = student_no;
st[s].y = b[0].first;
st[s].x = b[0].second;
}
}
void calculate() {
for(int i=0; i<n*n; i++) {
//int std_no = st[i].no;
int cy = st[i].y;
int cx = st[i].x;
int f_cnt = count_friend(i, cy, cx);
f_cnt = pow(10, (f_cnt-1));
if (f_cnt >= 1)
answer += f_cnt;
}
}
int main() {
scanf("%d", &n);
for(int i=0; i<n*n; i++) {
Student tmp;
int a, b, c, d, e;
scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
a--; b--; c--; d--; e--;
tmp.no = a;
tmp.friends[0] = b;
tmp.friends[1] = c;
tmp.friends[2] = d;
tmp.friends[3] = e;
st.push_back(tmp);
}
solve();
calculate();
printf("%d\n", answer);
return 0;
}
코드 설명
const int dy[4] = {-1, 0, 0, 1};
const int dx[4] = {0, -1, 1, 0};
struct Student {
int no;
int y, x;
int friends[4];
};
int n, answer;
int arr[21][21];
vector <Student> st;Student 구조체로 학생번호, 위치, 친구 정보 저장 vector 로 동적
int main() {
scanf("%d", &n);
for(int i=0; i<n*n; i++) {
Student tmp;
int a, b, c, d, e;
scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
a--; b--; c--; d--; e--; // 학생번호 0 부터 시작하도록 각 -- 해줌
tmp.no = a;
tmp.friends[0] = b;
tmp.friends[1] = c;
tmp.friends[2] = d;
tmp.friends[3] = e;
st.push_back(tmp);
}
solve(); //각 학생 배치
calculate(); // 점수 계산
printf("%d\n", answer);
return 0;
void solve() {
// init
memset(arr, -1, sizeof(arr)); // 초기 맵 -1 로 초기화 해줌 (학생 번호를 0 부터 시작하도록 했기 때문)
/**************************************************************/
for(int s=0; s<st.size(); s++) {
int student_no = st[s].no; // 학생 번호
int tmp_arr[n][n]; // 1번조건에서 사용할 임시 맵
// arr -> tmp_arr 로 copy
for(int i=0; i<n; i++)
for(int j=0; j<n; j++){
tmp_arr[i][j] = arr[i][j];
}
int max_f_value = -1; // 최대친구수 저장할 변수
vector <pair<int, int>> v; // 최대친구수를 얻을수 있는 좌표를 저장
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
// if not empty skip!
if(tmp_arr[i][j] != -1)
continue;
// s 의 친구 수 세기 (i,j) 위치에서
tmp_arr[i][j] = count_friend(s, i, j);
// 더 많은 친구를 만날수 있는 위치가 존재한다면
if(tmp_arr[i][j] > max_f_value) {
v.clear(); // 초기화
v.push_back(make_pair(i, j)); // 위치 집어넣기
max_f_value = tmp_arr[i][j]; // 최대 친구수 변경
}
// 최대친구수와 동일할 경우
else if(tmp_arr[i][j] == max_f_value) {
v.push_back(make_pair(i, j)); // 위치 집어넣기
}
}
// case 1 : 배치
if (v.size() == 1) {
arr[v[0].first][v[0].second] = student_no;
st[s].y = v[0].first;
st[s].x = v[0].second;
continue;
}
/**************************************************************/
int max_blank = -1;
vector <pair<int, int>> b;
// 인접빈칸개수 -> 위와 동일 로직
for(int i=0; i<v.size(); i++) {
int cy = v[i].first;
int cx = v[i].second;
int tmp_blank = count_blank(cy, cx);
if(tmp_blank > max_blank) {
max_blank = tmp_blank;
b.clear();
b.push_back(make_pair(cy, cx));
}
else if(tmp_blank == max_blank) {
b.push_back(make_pair(cy, cx));
}
}
// case 2 : 배치
if(b.size() == 1) {
arr[b[0].first][b[0].second] = student_no;
st[s].y = b[0].first;
st[s].x = b[0].second;
continue;
}
/**************************************************************/
sort(b.begin(), b.end(), compare); // 정렬, 맨 처음 오는 value 로 배치하면 된다.
// case 3 : 배치
arr[b[0].first][b[0].second] = student_no;
st[s].y = b[0].first;
st[s].x = b[0].second;
}
}// return how many close friend in y, x
int count_friend(int std_idx, int y, int x) {
int result = 0;
for(int i=0; i<4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
// 배열 밖일 경우 continue
if(ny < 0 || ny >= n || nx < 0 || nx >= n)
continue;
// 빈칸일 경우 continue
if (arr[ny][nx] == -1)
continue;
for(int f=0; f<4; f++) {
int friend_no = arr[ny][nx];
// 친구번호 존재할 경우 ++
if (friend_no == st[std_idx].friends[f]) {
result++;
}
}
}
return result;
}int count_blank(int y, int x) {
int result = 0;
for(int i=0; i<4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= n)
continue;
if(arr[ny][nx] == -1)
result++;
}
return result;bool compare (pair<int, int> a, pair<int, int> b) {
if(a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}void calculate() {
for(int i=0; i<n*n; i++) {
int cy = st[i].y;
int cx = st[i].x;
int f_cnt = count_friend(i, cy, cx);
f_cnt = pow(10, (f_cnt-1)); // 10^(f_cnt-1)
if (f_cnt >= 1)
answer += f_cnt;
}
}
초기 틀렸던 이유!
학생의 번호와 Vector <Student> std 의 인덱스가 다른 개념임.
이걸 동일시 해서 틀림
'알고리즘' 카테고리의 다른 글
| 13460 구슬탈출2 (0) | 2021.12.19 |
|---|---|
| 21609 상어중학교 (0) | 2021.12.13 |
| 14888 연산자 끼워넣기 ( DFS : 중복순열 || next_permutation) (0) | 2021.12.10 |
| 17143 낚시왕 (0) | 2021.12.09 |
| 19237 어른상어 (0) | 2021.12.08 |
'알고리즘' Related Articles
more
Comments