알고리즘/백준
21608_상어 초등학교
베리영young
2024. 6. 11. 13:08
사용 알고리즘: 구현 빡!
사용 언어: java
package src.SamsungA;
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/**
* 이런 식으로 출력된다;
* 0 -> 4 2 5 1 7
* 1 -> 3 1 9 4 5
* 2 -> 9 8 1 2 3
* 3 -> 8 1 9 3 4
* 4 -> 7 2 3 4 8
* 5 -> 1 9 2 5 7
* 6 -> 6 5 2 3 4
* 7 -> 5 1 9 2 8
* 8 -> 2 9 3 1 4
*/
public class Main_bj_21608_상어초등학교 {
static int n;
static int[][] map;
static ArrayList<ArrayList<Integer>> sittingOrder;
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,1,-1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
map = new int[n][n];
sittingOrder = new ArrayList<>(n*n);
for (int i = 0; i < n*n; i++) {
st = new StringTokenizer(br.readLine());
ArrayList<Integer> tmp = new ArrayList<>();
for (int j = 0; j < 5; j++) {
tmp.add(Integer.parseInt(st.nextToken()));
}
sittingOrder.add(tmp);
}
//
map[1][1] = sittingOrder.get(0).get(0); //첫 번째 학생은 무조건 여기
for (int studentNum = 1; studentNum < n*n; studentNum++) {
//3. 조건을 만족하는 칸이 여러 개라면, 행,열 번호가 가장 작은 칸으로 보내기 => Priority Queue 사용
PriorityQueue<Point> pq = new PriorityQueue<>(((o1, o2) -> {
if (o1.x != o2.x) {
return o1.x - o2.x; // x값 기준으로 비교
}
else {
return o1.y - o2.y; // x값이 같으면 y값 기준으로 비교
}
}));
//1. 빈 칸 중, 좋아하는 4학생이 인접 칸에 가장 많은 칸으로 자리 정하기.
pq = assignSeatsBasedLikeStudents(studentNum, pq);
//2. 인접 칸 중 빈 칸이 가장 많은 칸
pq = assignSeatsBasedEmpties(pq);
//자리 세팅!
Point assignHere = pq.peek(); //첫 번째
map[assignHere.x][assignHere.y] = sittingOrder.get(studentNum).get(0);
}
// for (int i = 0; i < n; i++) {
// System.out.println(Arrays.toString(map[i]));
// }
System.out.println(printSatisfaction());
}
private static int printSatisfaction() {
int satisfaction = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int buddies4dir = howManyBuddiesNearHere(i,j); //4방에 친구 몇 명?
satisfaction += buddiesScore(buddies4dir); //친구 수만큼 만족도 점수 반영 => 남들은 어떻게 했을까? 너무 코드가 별론데..
}
}
return satisfaction;
}
private static int howManyBuddiesNearHere(int i, int j) { //4방에 친구 몇 명?
int me = map[i][j];
int[] myBuddies = findBuddiesBaseMe(me);
int buddyCnt = 0;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (nx>=0 && nx<n && ny>=0 && ny<n) {
if( nearBuddy(map[nx][ny], myBuddies) ) buddyCnt++;
}
}
return buddyCnt;
}
private static boolean nearBuddy(int buddyNum, int[] myBuddies) {
for (int buddy : myBuddies) {
if (buddy == buddyNum) return true;
}
return false;
}
private static int[] findBuddiesBaseMe(int me) {
int[] buddies = new int[4];
for (int i = 0; i < n*n; i++) {
if (sittingOrder.get(i).get(0) == me) {
for (int j = 1; j <= 4 ; j++) {
buddies[j-1] = sittingOrder.get(i).get(j);
}
break;
}
}
return buddies;
}
private static int buddiesScore(int buddies) { //친구 수만큼 만족도 점수 반영
if (buddies==1) return 1;
if (buddies==2) return 10;
if (buddies==3) return 100;
if (buddies==4) return 1000;
return 0;
}
private static PriorityQueue<Point> assignSeatsBasedEmpties(PriorityQueue<Point> pq) {
PriorityQueue<Point> tmpPq = new PriorityQueue<>(((o1, o2) -> {
if (o1.x != o2.x) return o1.x - o2.x;
else return o1.y - o2.y;
}));
int empties = 0;
for (Point cur : pq) {
//4방 빈 칸 찾기
int curSeatEmpties = findEmpties4dir(cur);
if ( curSeatEmpties > empties ) {
empties = curSeatEmpties;
tmpPq.clear();
tmpPq.offer(cur);
} else if ( curSeatEmpties == empties ) {
tmpPq.offer(cur);
}
}
return tmpPq;
}
private static int findEmpties4dir(Point cur) {
int empties = 0;
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if (nx>=0 && nx<n && ny>=0 && ny<n) {
if (map[nx][ny] == 0) empties++;
}
}
return empties;
}
private static PriorityQueue<Point> assignSeatsBasedLikeStudents(int studentNum, PriorityQueue<Point> pq) {
int buddyCnt = 0; //여태 찾은 인접 칸에 친구가 가장 많은 자리의 친구 수
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) { //i,j 좌석이 빈 칸이면,
//4방 친구 찾기
int curSeatBuddies = findBuddies4dir(i,j, sittingOrder.get(studentNum));
if( curSeatBuddies > buddyCnt ) { //기존보다 친구가 많으면 pq 털고, 새로 넣기
buddyCnt = curSeatBuddies;
pq.clear();
pq.offer(new Point(i, j));
}
else if ( curSeatBuddies == buddyCnt ) { //기존과 같은 수면 pq에 추가만
pq.offer(new Point(i, j));
}
}
}
}
//
return pq;
}
private static int findBuddies4dir(int i, int j, ArrayList<Integer> buddies) {
int buddyCnt = 0;
int me = buddies.get(0);
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (nx>=0 && nx<n && ny>=0 && ny<n) {
if ( buddies.contains(map[nx][ny]) && map[nx][ny] != me ) {
buddyCnt++;
}
}
}
return buddyCnt;
}
}
느낀 점:
여기서 ArrayList<ArrayList<>>를 연습해 보려고 했다.
논리를 짠 거는 문제가 없었으나, 중간중간 정신이 나갈 뻔한 게 많았다.
논리 자체가 어려운 건 아니었지만, 복잡한 게 좀 있어서
집중해서 풀지 않았으면 못 풀었을 거 같다!
====================================
다른 사람 코드를 보니,
한 줄 입력 받고, 바로 map에서 들어갈 수 있는 좌표를 찾았음
ㄴ 이 때도 {pq에 좌표+4방향 친구 수+빈 칸 수}를 한꺼번에 입력 받아서(클래스로 만들어서) pq를 만들 때 4가지 조건을 한꺼번에 비교해서 가장 최우선이 되는 좌표가 pq 맨 앞에 오게 만듦.
seats.sort((s1, s2) -> {
if (s1.friendCnt == s2.friendCnt) { //1순위 : 좋아하는 학생이 많은 칸
if (s1.emptyCnt == s2.emptyCnt) { //2순위 : 비어있는 칸이 많은 칸
if (s1.y == s2.y) { //3순위 : 행의 번호가 가장 작은 칸
return s1.x - s2.x; //4순위 : 열의 번호가 가장 작은 칸
}
return s1.y - s2.y;
}
return s2.emptyCnt - s1.emptyCnt;
}
return s2.friendCnt - s1.friendCnt;
});천재적인데?