- 상어초등학교 친구들은 각자 좋아하는 친구들 근처(앞,뒤,좌,우)에 앉고 싶어 합니다.
- 주변에 좋아하는 친구가 많은 자리를 선호합니다.(1)
- 만약 이런 자리가 2개 이상이라면, 주변에 빈 자리가 많은 자리를 선호합니다.(2)
- 주변 빈자리까지 동일하다면, 최대한 앞자리를 선호합니다.(행이 더 작은 자리) (3-1)
- 만약 행까지 동일한 자리가 여러 개 있다면, 창가 자리를 선호합니다. (열이 더 작은 자리) (3-2)
- 친구들은 자기 차례 때 자리를 찾아 앉고, 내가 좋아하는 친구가 올 때까지 기다릴 수 없습니다.
- 내 차례 때, 내가 좋아하는 친구 가까운 자리가 하나도 없을 수 있습니다.
- 만약 좋아하는 친구 주위에 빈 자리가 없거나, 아직 좋아하는 친구가 자리 배치를 하지 않았다면
(2) --> (3-1) --> (3-2)의 선호도에 따라 앉을 자리를 선택합니다. - 당연하지만, 주인이 있는 자리에는 앉을 수 없습니다.
파랑은 빨강을 좋아합니다. 빨강은 교실의 중앙 자리에 배치되었네요.
(1)에 의해 4가지 자리가 후보로 올라 왔습니다. 후보 자리의 주변 빈 자리는 모두 2곳으로 동일합니다. (2)는 변별력을 갖지 못합니다.
다들 앞자리(3-1)와 창가쪽 자리(3-2)를 선호합니다.
여기서 (1,2)번 자리가 가장 앞 자리이므로, 이 자리가 선택되는 것입니다.
보라는 빨강을 좋아합니다. 이 경우 후보 자리는 위처럼 총 3가지가 있습니다. (1,2)는 이미 파랑이 차지해서 어쩔 수 없네요.(1)
다들 앞자리를 선호(3-1)하기에 (1,2)와 (2,3)이 최종 후보자리에 오르고,
창가(3-2)에 더 가까운 (1,2)가 선택됩니다.
저는 비어 있는 자리에 대해 각 선호도에 대한 가중치를 정해두고, 후보 자리 중 가장 마음에 드는 자리에 앉게 하였습니다.
상어초등학교 친구들은 자리 배정을 받기 전에, 비어 있는 모든 자리에 대해 평가를 합니다.
(1) - (2) - (3-1) - (3-2)를 거쳐 가장 선호하는 자리를 찾아 갑니다.
이를 위해서 우선순위 큐를 활용하였습니다.
자동 정렬을 위해 Comparable을 구현한 Seat(자리 클래스)를 우선순위 큐에 담고, 위의 기준에 따라 들어온 자리를 내림차순으로 갖고 있습니다. 따라서, 빈 자리를 모두 넣기만 하면 가장 선호할 만한 자리가 배정됩니다. 다만 복잡도를 줄이기 위해서, 가장 중요한 (1)조건으로 1차 필터링을 진행한 후, 남은 빈자리를 모두 넣습니다.
핵심 코드 참조)
static class Seat implements Comparable<Seat> {
int row;
int col;
int aroundFriends;
int aroundEmpty;
public Seat() {};
public Seat(int row, int col) {
this.row = row;
this.col = col;
this.aroundFriends = 0;
if (row + 1 <= N && classRoom[row + 1][col] == 0)
this.aroundEmpty++;
if (col + 1 <= N && classRoom[row][col + 1] == 0)
this.aroundEmpty++;
if (row - 1 != 0 && classRoom[row - 1][col] == 0)
this.aroundEmpty++;
if (col - 1 != 0 && classRoom[row][col - 1] == 0)
this.aroundEmpty++;
}
public void setAroundFriends(int[] prefer) {
for (int i = 0; i < 4; i++) {
if (prefer[i] != 0) {
if (row + 1 <= N && classRoom[this.row + 1][this.col] == prefer[i])
this.aroundFriends++;
if (col + 1 <= N && classRoom[this.row][this.col + 1] == prefer[i])
this.aroundFriends++;
if (row - 1 != 0 && classRoom[this.row - 1][this.col] == prefer[i])
this.aroundFriends++;
if (col - 1 != 0 && classRoom[this.row][this.col - 1] == prefer[i])
this.aroundFriends++;
}
}
}
@Override
public int compareTo(Seat o) {
// 주변에 좋아하는 친구가 더 많은 자리를 선택
if (this.aroundFriends > o.aroundFriends) {
return -1;
} else if (this.aroundFriends == o.aroundFriends) {
// 주변에 빈 자리가 더 많은 자리를 선택
if (this.aroundEmpty > o.aroundEmpty) {
return -1;
} else if (this.aroundEmpty == o.aroundEmpty) {
// 최대한 앞자리를 선택(행이 작은 쪽 선택)
if (this.row < o.row) {
return -1;
} else if (this.row == o.row) {
// 최대한 창가 자리를 선택(열이 작은 쪽 선택)
if (this.col < o.col)
return -1;
else
return 1;
} else
return 1;
} else
return 1;
} else
return 1;
}
}위 코드에서 aroundEmpty는 후보로 선택된 자리 주변에 빈 자리가 얼마나 있는지,
aroundFriends는 주변에 좋아하는 친구가 몇 명이나 있는지를 저장합니다.
compareTo 메소드를 오버라이딩하여 (1) - (2) - (3-1) - (3-2) 기준에 따라 자동으로 정렬되도록 하였습니다.
참고)
int compareTo(Object left, Object right) 메소드의 반환값에 따라 내림차순 / 오름차순 정렬이 결정됩니다.
return -1; --> 일차원 배열로 치면, left가 왼쪽에 와야 합니다.
return 1; --> 일차원 배열로 치면, right가 오른쪽에 와야 합니다.
따라서 left > right인 상황에서 return -1;을 한다면 오름차순 정렬이 됩니다.
반대로 left > right인 상황에서 return 1;을 한다면 내림차순 정렬이 됩니다.
논리 및 코드 설명)
코드1
설명1 형식
// 내가 좋아하는 친구 중 한 명이라도 배치되어 있는지 확인.
for (int j = 0; j < 4; j++) {
students[stNum].prefer[j] = Integer.parseInt(st.nextToken());
if (students[students[stNum].prefer[j]] != null)
tmp++;
}
if (tmp != 0) {~}자기 차례가 된 학생은, 먼저 자기가 좋아하는 친구가 자리를 선택했는지 확인합니다.(tmp)
boolean full = !(row + 1 <= N && classRoom[row + 1][col] == 0)
&& !(row - 1 != 0 && classRoom[row - 1][col] == 0)
&& !(col + 1 <= N && classRoom[row][col + 1] == 0)
&& !(col - 1 != 0 && classRoom[row][col - 1] == 0);있다면 그 친구 주변에 자리가 남았는지부터 확인합니다.
여기서 row+1 / row-1 / col+1 / col-1에 대한 검사를 진행합니다.
저는 배열에 대한 직관성을 높이기 위해서 시작점을 (0,0)이 아닌, (1,1)로 잡았습니다.
(new int[N+1][N+1])
if (!full) {
if (row + 1 <= N && classRoom[row + 1][col] == 0) {// 빈 자리 찾기
candidate = new Seat(row + 1, col);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
if (row - 1 != 0 && classRoom[row - 1][col] == 0) {
candidate = new Seat(row - 1, col);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
if (col + 1 <= N && classRoom[row][col + 1] == 0) {
candidate = new Seat(row, col + 1);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
if (col - 1 != 0 && classRoom[row][col - 1] == 0) {
candidate = new Seat(row, col - 1);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
} else {// 좋아하는 친구 근처 빈 자리가 하나도 없을 때,
for (int k = 1; k <= N; k++) {
for (int l = 1; l <= N; l++) {
if (classRoom[k][l] == 0)
pq.add(new Seat(k, l));
}
}
}그 친구 주변에 자리가 남았다면( if(!full) )
주변에 또다른 친구가 있는지, 자리의 위치는 어떤지 등, 자리에 대한 선호도를 계산합니다.
만약 친구 주변에 자리가 없다면 (2), (3-1), (3-2) 조건을 통해 가장 선호할 만한 자리를 배치받습니다. 후보 자리 주변의 빈 자리는 후보 Seat 클래스가 생성되며 자동으로 검사합니다.
현재 자리 배정 차례인 학생의 좋아하는 친구 정보를 넘겨받은 후, (1) 검사를 진행합니다.
선호도 계산이 끝나면 우선순위 큐에 넣습니다. compareTo 기준에 따라 가장 선호도가 높을 만한 자리가 큐 맨앞에 위치합니다.
Seat tmpSeat = pq.poll();
classRoom[tmpSeat.row][tmpSeat.col] = stNum;
students[stNum].row = tmpSeat.row;
students[stNum].col = tmpSeat.col;
students[stNum].seat = true;우선순위 큐의 맨앞의 자리를 꺼내서, 현재 차례를 기다리는 학생에게 배정합니다.
else {// 제일 처음 배치되는 친구이거나, 아직 좋아하는 친구가 배치 안 되었을 경우.
for (int k = 1; k <= N; k++) {
for (int j = 1; j <= N; j++) {
if (classRoom[k][j] == 0)
pq.add(new Seat(k, j));
}
}
}아직 좋아하는 친구가 자리를 배치받지 못했다면(else) 교실의 빈 자리 중 조건 (2), (3-1), (3-2)를 통해 가장 선호할 만한 자리를 배치받습니다.
(맨 처음 학생의 경우도 이 조건문을 들어옵니다.)
int sum = 0;
for (int row = 1; row <= N; row++) {
for (int col = 1; col <= N; col++) {
int around = 0;
int st = classRoom[row][col];
int[] prefer = students[st].prefer;
for (int k = 0; k < 4; k++) {
if (row + 1 <= N && classRoom[row + 1][col] == prefer[k])
around++;
if (col + 1 <= N && classRoom[row][col + 1] == prefer[k])
around++;
if (row - 1 != 0 && classRoom[row - 1][col] == prefer[k])
around++;
if (col - 1 != 0 && classRoom[row][col - 1] == prefer[k])
around++;
}
if (around == 1)
sum += 1;
else if (around == 2)
sum += 10;
else if (around == 3)
sum += 100;
else if (around == 4)
sum += 1000;
else
sum += 0;
}
}모든 학생의 자리 배치가 끝났다면, 각 학생들에게 만족도 조사를 실시합니다.
만족도는 자기 자리 주변에 좋아하는 친구가 몇 명이나 있는지만 영향을 미칩니다.
최종 코드)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int[][] classRoom;
static Student[] students;
static int N;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bfr.readLine());
classRoom = new int[N + 1][N + 1];
students = new Student[N * N + 1];
for (int i = 0; i < N * N; i++) {
StringTokenizer st = new StringTokenizer(bfr.readLine());
PriorityQueue<Seat> pq = new PriorityQueue<>();
int stNum = Integer.parseInt(st.nextToken());
students[stNum] = new Student();
students[stNum].prefer = new int[4];
int tmp = 0;
// 내가 좋아하는 친구 중 한 명이라도 배치되어 있는지 확인.
for (int j = 0; j < 4; j++) {
students[stNum].prefer[j] = Integer.parseInt(st.nextToken());
if (students[students[stNum].prefer[j]] != null)
tmp++;
}
// 자리 배치 시작
if (tmp != 0) {
for (int j = 0; j < 4; j++) {
// 좋아하는 애의 근접 좌석 확인
// prefer[] 배열이 모두 0이라면, 제일 처음 좌석 배치받은 거임.
// 최대 16가지의 좌석 배치가 있을 수 있다.
if (students[students[stNum].prefer[j]] != null
&& students[students[stNum].prefer[j]].seat == true) {
int row = students[students[stNum].prefer[j]].row;
int col = students[students[stNum].prefer[j]].col;
Seat candidate;
boolean full = !(row + 1 <= N && classRoom[row + 1][col] == 0)
&& !(row - 1 != 0 && classRoom[row - 1][col] == 0)
&& !(col + 1 <= N && classRoom[row][col + 1] == 0)
&& !(col - 1 != 0 && classRoom[row][col - 1] == 0);
if (!full) {
if (row + 1 <= N && classRoom[row + 1][col] == 0) {// 빈 자리 찾기
candidate = new Seat(row + 1, col);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
if (row - 1 != 0 && classRoom[row - 1][col] == 0) {
candidate = new Seat(row - 1, col);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
if (col + 1 <= N && classRoom[row][col + 1] == 0) {
candidate = new Seat(row, col + 1);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
if (col - 1 != 0 && classRoom[row][col - 1] == 0) {
candidate = new Seat(row, col - 1);
candidate.setAroundFriends(students[stNum].prefer);
pq.add(candidate);
}
} else {// 좋아하는 친구 근처 빈 자리가 하나도 없을 때,
for (int k = 1; k <= N; k++) {
for (int l = 1; l <= N; l++) {
if (classRoom[k][l] == 0)
pq.add(new Seat(k, l));
}
}
}
}
}
} else {// 제일 처음 배치되는 친구이거나, 아직 좋아하는 친구가 배치 안 되었을 경우.
for (int k = 1; k <= N; k++) {
for (int j = 1; j <= N; j++) {
if (classRoom[k][j] == 0)
pq.add(new Seat(k, j));
}
}
}
Seat tmpSeat = pq.poll();
classRoom[tmpSeat.row][tmpSeat.col] = stNum;
students[stNum].row = tmpSeat.row;
students[stNum].col = tmpSeat.col;
students[stNum].seat = true;
}
// 모든 친구 배치 끝
cal();
bfr.close();
}
static void cal() {
int sum = 0;
for (int row = 1; row <= N; row++) {
for (int col = 1; col <= N; col++) {
int around = 0;
int st = classRoom[row][col];
int[] prefer = students[st].prefer;
for (int k = 0; k < 4; k++) {
if (row + 1 <= N && classRoom[row + 1][col] == prefer[k])
around++;
if (col + 1 <= N && classRoom[row][col + 1] == prefer[k])
around++;
if (row - 1 != 0 && classRoom[row - 1][col] == prefer[k])
around++;
if (col - 1 != 0 && classRoom[row][col - 1] == prefer[k])
around++;
}
if (around == 1)
sum += 1;
else if (around == 2)
sum += 10;
else if (around == 3)
sum += 100;
else if (around == 4)
sum += 1000;
else
sum += 0;
}
}
System.out.println(sum);
}
static class Student {
int row;
int col;
int[] prefer;
boolean seat = false;
public Student() {
}
public Student(int row, int col) {
this.row = row;
this.col = col;
this.seat = true;
}
}
static class Seat implements Comparable<Seat> {
int row;
int col;
int aroundFriends;
int aroundEmpty;
public Seat() {
};
public Seat(int row, int col) {
this.row = row;
this.col = col;
this.aroundFriends = 0;
if (row + 1 <= N && classRoom[row + 1][col] == 0)
this.aroundEmpty++;
if (col + 1 <= N && classRoom[row][col + 1] == 0)
this.aroundEmpty++;
if (row - 1 != 0 && classRoom[row - 1][col] == 0)
this.aroundEmpty++;
if (col - 1 != 0 && classRoom[row][col - 1] == 0)
this.aroundEmpty++;
}
public void setAroundFriends(int[] prefer) {
for (int i = 0; i < 4; i++) {
if (prefer[i] != 0) {
if (row + 1 <= N && classRoom[this.row + 1][this.col] == prefer[i])
this.aroundFriends++;
if (col + 1 <= N && classRoom[this.row][this.col + 1] == prefer[i])
this.aroundFriends++;
if (row - 1 != 0 && classRoom[this.row - 1][this.col] == prefer[i])
this.aroundFriends++;
if (col - 1 != 0 && classRoom[this.row][this.col - 1] == prefer[i])
this.aroundFriends++;
}
}
}
@Override
public int compareTo(Seat o) {
// 주변에 좋아하는 친구가 더 많은 자리를 선택
if (this.aroundFriends > o.aroundFriends) {
return -1;
} else if (this.aroundFriends == o.aroundFriends) {
// 주변에 빈 자리가 더 많은 자리를 선택
if (this.aroundEmpty > o.aroundEmpty) {
return -1;
} else if (this.aroundEmpty == o.aroundEmpty) {
// 최대한 앞자리를 선택(행이 작은 쪽 선택)
if (this.row < o.row) {
return -1;
} else if (this.row == o.row) {
// 최대한 창가 자리를 선택(열이 작은 쪽 선택)
if (this.col < o.col)
return -1;
else
return 1;
} else
return 1;
} else
return 1;
} else
return 1;
}
}
}
한땀한땀오타없이