Algorithm/백준 문제풀이
[백준] 21608 상어 초등학교 - Java
너지살
2023. 10. 8. 23:09
문제 출저
https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
문제 풀이
학생 번호와 학생이 좋아하는 학생의 번호 4개가 주어진다.
이 때 교실의 한 변이 n일 때, n*n명의 학생을 겹치지 않게 교실에 배치한다.
상하좌우 인접한 4곳의 좋아하는 학생수에 따라 만족도 점수가 부여된다.
순서대로 학생들을 배치한 다음 만족도 점수를 계산하는게 이 문제의 요구사항 입니다.
구현
학생을 배치할 때는 3가지 조건에 따라 앉힙니다.
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
먼저 한 학생을 선택해 배치하려 합니다.
이 학생이 좋아하는 학생이 배치되어 있는지 확인합니다.
학생이 배치되어 있다면 배치되어 있는 학생의 4방향 +1을 합니다.
그리고 조건에 따라 인접한 학생 수가 많은 순, 공백이 많은 순, 행과 열의 번호가 작은 순으로 구합니다.
만약, 좋아하는 학생이 있지만 근처에 자리가 없다면 친구가 없을 때 배치하는 함수를 돌립니다.
이 함수는 빈 공간 중엔 인근에 공간이 많은 순, 행과 열의 번호가 적은 순으로 학생을 앉히는 함수 입니다.
위의 함수들을 통해 학생들을 전부 앉힌 후 n*n 배열은 순회하면 만족도를 계산합니다.
소스 코드
package baekjoon.backjoon10.day0110.day08;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/*
상어 초등학교
https://www.acmicpc.net/problem/21608
1. 비어있는 칸 중 좋아하는 학생이 많이 인접한 칸에 자리를 정한다.
2. 1의 조건이 여러개면 비어있는 칸이 가장 많은 칸으로 간다.
3. 2를 만족하는 칸이 많으면 행의 번호, 열의 번호 작은 칸으로 간다.
3
5 6 1 8 4
6 7 4 8 2
7 3 1 6 9
4 1 6 9 7
8 5 4 6 3
2 6 4 3 7
1 2 5 8 4
9 4 7 5 6
3 4 1 6 5
44
*/
public class B21608 {
static int n;
static int[] order; // 학생 배치 순서
static int[][] friendArr; // 학생 별 좋아하는 친구들 저장
static int[][] board; // 배치
static int[][] room; // 교실
static boolean[] visited; // 학생이 배치되어 있는지 여부 확인
static int[] dx = {1,0,-1,0};
static int[] dy = {0,-1,0,1};
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
order = new int[n*n];
friendArr = new int[n*n+1][4];
StringTokenizer st = null;
for(int i = 1; i <= n*n; i++) {
st = new StringTokenizer(br.readLine());
int student = Integer.parseInt(st.nextToken());
order[i-1] = student;
for(int j = 0; j < 4; j++) {
int friend = Integer.parseInt(st.nextToken());
friendArr[student][j] = friend;
}
}
board = new int[n*n+1][2];
room = new int[n][n];
visited = new boolean[n*n+1];
// 자리 배치
for(int i = 0; i < n*n; i++) {
place(order[i]);
}
// 만족도 조사
answer = 0;
satisfiction();
System.out.println(answer);
}
public static void satisfiction() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
answer += scoreCheck(i,j,room[i][j]);
}
}
}
public static int scoreCheck(int y, int x, int number) {
int result = 0;
int count = 0;
for(int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if(scoreBoardCheck(ny, nx)) {
for(int j = 0; j < 4; j++) {
if(friendArr[number][j] == room[ny][nx]) {
count++;
}
}
}
}
if(count == 0) {
result = 0;
}
else if(count == 1) {
result = 1;
}
else if(count == 2) {
result = 10;
}
else if(count == 3) {
result = 100;
}
else if(count == 4) {
result = 1000;
}
return result;
}
public static boolean scoreBoardCheck(int y, int x) {
if(y >= 0 && y < n && x >= 0 && x < n) {
return true;
}
else {
return false;
}
}
/*
학생이 들어왔을 때 어디에 배치할지 board
1. 좋아하는 학생이 배치되어 있는 경우 4방향 탐색
인접한 학생 수 Count 큰 거 가져옴
y,x가 낮은거에 선택
2. 학생이 없는 경우 인접한 곳에 비어있는 칸이 많은 곳에 배치
*/
public static void place(int number) {
// System.out.println(number);
// 좋아하는 학생이 배치 되어 있는지 확인
Queue<Integer> likeQue = new LinkedList<>();
for(int i = 0; i < 4; i++) {
int friend = friendArr[number][i];
if(visited[friend]) {
likeQue.add(friend);
}
}
// 좋아하는 친구가 있을 경우
if(likeQue.size() >= 1) {
// 좋아하는 친구가 있지만 배치를 할 수 없는 경우
if(placeHaveFriend(number, likeQue)) {
// System.out.println("work");
placeNoFriend(number);
}
}
// 좋아하는 친구가 없을 경우. 가장 빈 칸 많은 곳 행과 열이 작으면서
else {
placeNoFriend(number);
}
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < n; j++) {
// System.out.print(room[i][j] + " ");
// }
// System.out.println();
// }
//
// System.out.println();
}
// 좋아하는 친구가 없는 경우, 빈 칸이 가장 많은 곳
public static void placeNoFriend(int number) {
int selecty = -1;
int selectx = -1;
int result = -1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(room[i][j] != 0) {
continue;
}
int blank = countBlank(i,j);
if(result < blank) {
result = blank;
selecty = i;
selectx = j;
}
else if(result == blank) {
if(i < selecty) {
selecty = i;
selectx = j;
}
else if(i == selecty && j < selectx) {
selecty = i;
selectx = j;
}
}
}
}
room[selecty][selectx] = number;
board[number][0] = selecty;
board[number][1] = selectx;
visited[number] = true;
}
// 근처에 빈 칸 갯수 세기
public static int countBlank(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(check(ny, nx)) {
result++;
}
}
return result;
}
// 좋아하는 친구가 이미 배치되어 있는 경우
public static boolean placeHaveFriend(int number, Queue<Integer> likeQue) {
// 인접한 곳에 좋아하는 학생이 가장 많은 칸 찾기
int[][] simulation = new int[n][n];
int result = 0;
int blank = 0;
int selecty = -1;
int selectx = -1;
while(!likeQue.isEmpty()) {
Integer friend = likeQue.poll();
int friendy = board[friend][0];
int firendx = board[friend][1];
for(int i = 0; i < 4; i++) {
int ny = friendy + dy[i];
int nx = firendx + dx[i];
if(check(ny,nx)) {
simulation[ny][nx] += 1;
if(simulation[ny][nx] > result) {
result = simulation[ny][nx];
blank = countBlank(ny,nx);
selecty = ny;
selectx = nx;
}
else if(simulation[ny][nx] == result) {
int newBlank = countBlank(ny,nx);
if(newBlank > blank) {
blank = newBlank;
selecty = ny;
selectx = nx;
}
else if(newBlank == blank) {
if(ny < selecty) {
selecty = ny;
selectx = nx;
}
if(ny == selecty && nx < selectx) {
selecty = ny;
selectx = nx;
}
}
}
}
}
}
if(selecty == -1 && selectx == -1) {
return true;
}
else {
room[selecty][selectx] = number;
board[number][0] = selecty;
board[number][1] = selectx;
visited[number] = true;
return false;
}
}
public static boolean check(int y, int x) {
if(y >= 0 && y < n && x >= 0 && x < n && room[y][x] == 0) {
return true;
}
else {
return false;
}
}
}