#include <iostream>
#include <vector>
#include <algorithm> // sort
using namespace std;
// 학생 정보
struct STUDENT{
int num; // 학생 번호
int fav[4]; // 학생이 좋아하는 친구
};
struct POSITION{
int x, y;
int blanks;
int friends;
};
int map[21][21]; // 자리
vector<STUDENT> st(401); // 학생 정보
int N;
int ans = 0;
// 인접 좌표
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
// 만족도 - 굳이 pow 쓰지말자
int score[5] = {0, 1, 10, 100, 1000};
int main(int argc, char** argv){
scanf("%d", &N);
for(int i = 1; i <= N * N; i++){
scanf("%d", &st[i].num); // 학생 순서 입력받기
for(int j = 0; j < 4; j++){
scanf("%d", &st[i].fav[j]); // 좋아하는 학생 입력받기
}
}
// 학생 앉히기
for(int i = 1; i <= N * N; i++){
STUDENT student = st[i];
vector<POSITION> pos(5); // 총 주위 4칸 탐색
int bmax = 0, fmax = 0;
for(int j = 1; j <= N; j++){
for(int k = 1; k <= N; k++){
// 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정함
// 비어있지 않으면 패스 - if문 너무 많이 써서 따로 빼려고 이렇게 작성
if(map[j][k] != 0){
continue;
}
int bcnt = 0, fcnt = 0;
// 좌표 방향 설정 idx값은 이렇게 설정하는게 더 확인하기 쉽다.
for(int dir = 0; dir < 4; dir++){
int nx = j + dx[dir];
int ny = k + dy[dir];
// 보드 벗어나는 좌표
if(nx < 1 || ny < 1 || nx > N || ny > N){
continue;
}
// 빈 칸인 경우와 친구의 수를 한 번에 센다!
// 빈 칸인 경우
if(map[nx][ny] == 0){
bcnt++;
} else if(map[nx][ny] == student.fav[0] || map[nx][ny] == student.fav[1]
|| map[nx][ny] == student.fav[2] || map[nx][ny] == student.fav[3]){
fcnt++;
}
}
// 친구 많은 칸을 넣음
if(fcnt > fmax){
pos.clear(); // 벡터 초기화 - 친구 많으면 후보 요소 없음
pos.push_back({j, k, fcnt, bcnt});
// 후보칸의 요소 저장
fmax = fcnt;
bmax = bcnt;
continue;
} else if(fcnt == fmax){
// 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
if(bcnt >= bmax){
pos.clear();
pos.push_back({j, k, fcnt, bcnt});
bmax = bcnt;
} else {
// 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
pos.push_back({j, k, fcnt, bcnt});
}
}
}
// for(int i = 1; i <= N; i++){
// for(int j = 1; j <= N; j++){
// printf("%d", map[i][j]);
// }
// printf("\n");
// }
// printf("------\n");
}
// 학생 배치
map[pos[0].x][pos[0].y] = student.num;
}
// 학생 만족도 총 합
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
int cnt = 0;
// 상하좌우 탐색
for(int dir = 0; dir < 4; dir++){
int nx = i + dx[dir];
int ny = j + dy[dir];
if(nx < 1 || ny < 1 || nx > N || ny > N){
continue;
}
for(int k = 0; k < st.size(); k++){
if(st[k].num == map[i][j]){
if(map[nx][ny] == st[k].fav[0] || map[nx][ny] == st[k].fav[1]
|| map[nx][ny] == st[k].fav[2] || map[nx][ny] == st[k].fav[3]){
cnt++;
}
}
}
}
ans += score[cnt];
}
}
// for(int i = 1; i <= N; i++){
// for(int j = 1; j <= N; j++){
// printf("%d", map[i][j]);
// }
// printf("\n");
// }
printf("%d", ans);
return 0;
}
와 구현 노가다 문제는 진짜 진짜 어렵다... 시간 정말 오래 걸린듯
pos에는 후보칸의 위치와 그에 따른 정보가 들어간다. 따라서 인접 친구가 더 많은 경우만 후보자로 정한다. clear를 사용하여 가장 강력한 후보를 제일 앞으로 보낸다.
하지만, 2번 조건은 다르다. 비어있는 칸이 많은 칸으로 자리를 정하고, 3번 조건에 따르면 행의 번호가 작은 칸 -> 열의 번호가 작은 칸이므로 부등호를 '>'가 아닌 '>='을 사용하여 해당 경우도 만족시키도록 한다. (for문을 사용해 작은 부분부터 순회하기 때문에 부등호로 해당 경우도 처리할 수 있다.) 이 때도 가장 강력한 후보자이므로 clear를 시켜 후보자를 제일 앞으로 보낸다.
하지만, 인접 친구도 없고 비어있는 칸도 없는 경우에는 그냥 넣어줘야한다. 때문에 마지막에 else문에 그 경우에도 예외처리를 해준다. 하지만 이 경우에는 pos.clear()를 해주면 안된다. 그러하면 예제에서 4를 배치시킬때
000
040
000
이 아닌
000
000
004
가 된다. 그 이유는 clear시켜서 마지막으로 위치가 표시되기 때문이다. clear를 시키지 않아야 제일 강력한 후보자를 지우지 않을 수 있다.
그래도 이번 문제로 골드 3을 찍었다... 하지만 실력은 골드 3이 아니지 짭골드다.