Java/코딩테스트
백준 21608
Bubbles
2023. 10. 11. 18:10
🦈 백준 21608 : 상어 초등학교
https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
🦈 앞에서 풀었던 상어의 파이어볼보다 더 열받는 문제였다.
🦈 문제 순서대로 구현하면 되는 문제이기는 하지만, 조건이 매우 복잡하여 틀린부분을 수정하는데 오래 걸렸다.
🦈 나는 아래 부분을 실수했었다.
- 마지막 칸 하나만 남았을 때는 무조건 그 칸으로 들어갈 수 밖에 없다.
- 방문 처리를 확실히 할 것. 학생 번호를 편의상 0부터 배치했더니, 이미 자리가 있는데 없다고 생각하고 덮어씌워지는 경우가 계속 발생하였다.
🦈 이걸 제대로 카운트를 안하니깐 이미 앉아있는 자리를 빼앗는(...)다던가 아예 안 앉는 그런 불상사도 있었다.
🦈 그리고 학생 번호는 1부터 시작하다보니 처음에 0이면 학생이 배치되지 않은 좌석이라고 생각했는데, 내가 그냥 0부터 배치해서 이미 자리가 있는데도 덮어씌워지는 경우도 생겼다.
🦈 주요 로직
🦈 좌석찾기 : findSeat
- 좋아하는 애가 많은 곳 찾기
- 좋아하는 애들 중, 좌석이 배치된 애들이 있다면, 얘네 주변 4방향 좌석에 점수를 준다.
- 그리고 max를 구한다.
- 만약 max가 1개라면 얘가 바로 배치될 공간이고, 좋아하는 애들이 배치되지 않았거나, 여러 자리가 후보라면 빈칸 탐색 시작
private static Pos findSeat(int index) {
temp = new int[n][n];
for (int s: likes[index]) {
if (isSit[s] != null) {
for (int i = 0; i < 4; i++) {
int nextX = isSit[s].x + dirX[i];
int nextY = isSit[s].y + dirY[i];
if (!isValid(nextX, nextY)) {
continue;
}
if (map[nextX][nextY] != 0) {
continue;
// 이미 누가 앉아있다면 거긴 못앉으니까
}
temp[nextX][nextY]++;
}
}
}
ArrayList<Pos> posList = maxCount(findMax());
Pos answer;
if (posList.size() == 1) {
answer = posList.get(0);
}
else {
answer = findEmptyMax(posList);
}
return answer;
}
- 빈칸 많은 곳 찾기 : findEmptyMax를 findSeat에서 내부 호출
- 앞에서 후보들을 리스트 형태로 매개변수로 받아와서, 하나씩 검사한다.
- 후보 리스트 만큼의 배열을 하나 만들고, 그 배열에 각 장소별 점수를 계산한다.
- 후보가 이미 차지된 경우도 있을 수 있는데, 이 경우에는 선택불가능하므로 -1로 점수를 넣고 continue처리 해줌.
- 그 뒤 max값을 찾는다.
- 그런데 이때, 모든 칸이 다 주변 빈칸이 0인 경우 (딱 한칸만 남아있다거나) 이런 경우에는 모든 칸 중 착석 안된 칸 밖에 못 앉히므로 그 칸이 자동으로 된다.
- max값이 다 똑같다면 가장 왼쪽 위에 있는 행이 정답이므로(문제의 조건에 따라) 가장 먼저 max가 나온 곳이 답이다.
private static Pos findEmptyMax(ArrayList<Pos> posList) {
int[] arr = new int[posList.size()];
int max = -11;
for (int i = 0; i < posList.size(); i++) {
int count = 0;
if (map[posList.get(i).x][posList.get(i).y] != 0) {
arr[i]= -1;
continue;
}
for (int j = 0; j < 4; j++) {
int nextX = posList.get(i).x + dirX[j];
int nextY = posList.get(i).y + dirY[j];
if (!isValid(nextX, nextY)) {
continue;
}
if (map[nextX][nextY] == 0) {
count++;
}
}
arr[i] = count;
}
for (int i = 0; i < posList.size(); i++) {
max = Math.max(max, arr[i]);
}
for (int i = 0; i < posList.size(); i++) {
if (max == arr[i]) {
max = i;
break;
}
}
if (completed == n*n-1) {
for (int i = 0 ; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) {
return new Pos(i, j);
}
}
}
}
return posList.get(max);
}
🦈 가중치 계산하기
- 각 좌석별로, 자기 주변 4방향에 대해 그 좌석에 앉은 애가 좋아하는 애가 몇 명 앉아있는지를 계산
- 주변에 0명이라면 그대로 0
- 1명 이상이라면 10 ^ around - 1 이 점수이다.
private static int findAround(int index) {
Pos pos = isSit[index];
ArrayList<Integer> like = likes[index];
int count = 0;
for (int i = 0; i < 4; i++) {
int nextX = pos.x + dirX[i];
int nextY = pos.y + dirY[i];
if (!isValid(nextX, nextY)) {
continue;
}
for (Integer likeIndex : like) {
if (isSit[likeIndex].x == nextX && isSit[likeIndex].y == nextY) {
count++;
}
}
}
return count;
}
🦈 전체코드
import java.io.*;
import java.util.*;
public class p21608 {
static int n, completed;
static Pos[] isSit;
static int[][] map;
static int[][] temp;
static ArrayList<Integer>[] likes;
static int[] dirX = { -1, 1, 0, 0 };
static int[] dirY = { 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());
isSit = new Pos[n*n+1];
map = new int[n][n];
likes = new ArrayList[n*n+1];
int[] order = new int[n*n];
int answer = 0;
completed = 0;
for (int i = 0; i < n*n+1; i++) {
likes[i] = new ArrayList<>();
}
for (int i = 0; i < n*n; i++) {
st = new StringTokenizer(br.readLine());
int index = Integer.parseInt(st.nextToken());
order[i] = index;
for (int j = 0; j < 4; j++) {
likes[index].add(Integer.parseInt(st.nextToken()));
}
}
for (int i = 0; i < n*n; i++) {
int index = order[i];
Pos seat = findSeat(index);
isSit[index] = seat;
map[seat.x][seat.y] = index;
completed++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int around = findAround(map[i][j]);
if (around != 0) {
answer += Math.pow(10, (double) around - 1);
}
}
}
System.out.println(answer);
}
private static int findAround(int index) {
Pos pos = isSit[index];
ArrayList<Integer> like = likes[index];
int count = 0;
for (int i = 0; i < 4; i++) {
int nextX = pos.x + dirX[i];
int nextY = pos.y + dirY[i];
if (!isValid(nextX, nextY)) {
continue;
}
for (Integer likeIndex : like) {
if (isSit[likeIndex].x == nextX && isSit[likeIndex].y == nextY) {
count++;
}
}
}
return count;
}
private static Pos findSeat(int index) {
temp = new int[n][n];
for (int s: likes[index]) {
if (isSit[s] != null) {
for (int i = 0; i < 4; i++) {
int nextX = isSit[s].x + dirX[i];
int nextY = isSit[s].y + dirY[i];
if (!isValid(nextX, nextY)) {
continue;
}
if (map[nextX][nextY] != 0) {
continue;
// 이미 누가 앉아있다면 거긴 못앉으니까
}
temp[nextX][nextY]++;
}
}
}
ArrayList<Pos> posList = maxCount(findMax());
Pos answer;
if (posList.size() == 1) {
answer = posList.get(0);
}
else {
answer = findEmptyMax(posList);
}
return answer;
}
private static Pos findEmptyMax(ArrayList<Pos> posList) {
int[] arr = new int[posList.size()];
int max = -11;
for (int i = 0; i < posList.size(); i++) {
int count = 0;
if (map[posList.get(i).x][posList.get(i).y] != 0) {
arr[i]= -1;
continue;
}
for (int j = 0; j < 4; j++) {
int nextX = posList.get(i).x + dirX[j];
int nextY = posList.get(i).y + dirY[j];
if (!isValid(nextX, nextY)) {
continue;
}
if (map[nextX][nextY] == 0) {
count++;
}
}
arr[i] = count;
}
for (int i = 0; i < posList.size(); i++) {
max = Math.max(max, arr[i]);
}
for (int i = 0; i < posList.size(); i++) {
if (max == arr[i]) {
max = i;
break;
}
}
if (completed == n*n-1) {
for (int i = 0 ; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) {
return new Pos(i, j);
}
}
}
}
return posList.get(max);
}
private static int findMax() {
int max = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
max = Math.max(max, temp[i][j]);
}
}
return max;
}
private static ArrayList<Pos> maxCount(int max) {
ArrayList<Pos> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (temp[i][j] == max) {
list.add(new Pos(i, j));
}
}
}
return list;
}
private static boolean isValid(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n) {
return false;
}
return true;
}
static class Pos {
int x;
int y;
Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
}