반응형
출처: https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
구현문제입니다.
1. 단순구현으로 해결했다.
결론적으로 반복문을 통해서 각각의 학생들의 자리를 픽스시켜 주면 되기 때문에, 천천히 조건에 맞게 구현하면 된다.
2. 3가지 조건중 1번, 2번을 통해서 각각의 학생별로 해당하는 위치를 도출했다. 3번은 우선순위에 의해서 일반적인 반복문을 사용하면 자동으로 결정됨.
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
그런데 왠 런타임 에러??
주의점은 만약 좋아하는 친구와, 빈칸 모두 없는 상황일때는 3번 조건에 의해서 가장 가까운 칸을 선택하도록 예외처리를 추가해주어야 한다. (본 코드 storePosition 함수 아래쪽 참고)
정답 코드
#include <iostream>
#include <vector>
using namespace std;
vector <int> friends[401];
vector <int> vec; // 순서저장
int arr[25][25] = { 0, }; // 위치가 픽스 되면
int n = 0;
int result = 0;
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
void storePosition(int& y, int& x, int v) {
int rf = 0;
int rb = 0;
int ry = 0;
int rx = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] != 0)
continue;
int cy = i;
int cx = j;
int fav = 0;
int bla = 0;
for (int k = 0; k < 4; k++) {
int ny = cy + y_ar[k];
int nx = cx + x_ar[k];
if (ny < 1 || ny > n || nx < 1 || nx > n)
continue;
for (int u = 0; u < 4; u++) {
if (arr[ny][nx] == friends[v][u])
fav++;
else if(arr[ny][nx] == 0)
bla++;
}
}
if (fav > rf) {
rf = fav;
rb = bla;
ry = cy;
rx = cx;
}
else if (fav == rf) {
if (bla > rb) {
rb = bla;
ry = cy;
rx = cx;
}
}
}
}
if (ry == 0 && rx == 0) { // 중요
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] == 0) {
ry = i, rx = j;
break;
}
}
if (ry != 0 && rx != 0)
break;
}
}
y = ry, x = rx;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n*n; i++) {
int temp;
int temp2[4];
cin >> temp;
vec.push_back(temp);
for (int j = 0; j < 4; j++) {
cin >> temp2[j];
friends[temp].push_back(temp2[j]);
}
}
for (int i = 0; i < n*n; i++) {
int v = vec[i];
int y = 0; int x = 0;
storePosition(y, x, v);
arr[y][x] = v;
}
// 점수 계산
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int cy = i;
int cx = j;
int cnt = 0;
for (int k = 0; k < 4; k++) {
int ny = cy + y_ar[k];
int nx = cx + x_ar[k];
if (ny < 1 || ny > n || nx < 1 || nx > n)
continue;
for (int u = 0; u < 4; u++) {
if (arr[ny][nx] == friends[arr[cy][cx]][u])
cnt++;
}
}
if (cnt == 1)
result += 1;
else if (cnt == 2)
result += 10;
else if (cnt == 3)
result += 100;
else if (cnt == 4)
result += 1000;
}
}
cout << result << endl;
return 0;
}
반응형
'알고리즘 > 시뮬레이션' 카테고리의 다른 글
| [백준] 16918-봄버맨(C++) (0) | 2021.07.12 |
|---|---|
| [백준] 20058-마법사 상어와 파이어스톰(C++) (0) | 2021.04.03 |
| [백준] 20057-마법사 상어와 토네이도(C++) (2) | 2021.03.30 |
| [백준] 20055-컨베이어 벨트 위의 로봇(C++) (0) | 2021.03.21 |
| [백준] 8911-거북이(C++) (0) | 2021.01.10 |
