https://www.acmicpc.net/problem/21608
상어 초등학교
문제의 조건에 맞게 구현하면 되는 문제다.
문제의 자세한 내용은 링크를 통해 확인하고 문제의 조건을 확인하자.
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
풀이
처음에는 그냥 문제의 예시에 맞게 구현을 하려고 했다.
우선 처음 자리해야할 학생은 교실의 크기에 상관없이 무조건 (2,2)에 자리하게 된다. 그 다음 들어오는 학생의 위치를 정해주는 것이 이제 중요하다.
처음에는 이전에 자리한 학생을 기준으로 지금 들어온 학생의 위치를 정해주려 했지만 지금 들어온 학생이 이전에 자리한 학생이 아니라 전전에 자리한 학생을 선호할 경우 정확한 자리를 찾아주지 못하는 문제가 있다.
그래서 n의 범위가 3 ≤ N ≤ 20 이기때문에 그냥 교실의 0인 좌표의 상하좌우를 살펴 빈 자리는 몇 개인지, 주변에 지금 들어오는 학생이 선호하는 사람이 몇 명인지를 체크해 count를 증가시켜 max가 변경되면 그 때 좌표를 기억하는 형태로 구현했다.
private static void findPos(int[] pref, int cur) {
int x = -1;
int y = -1;
int prefMax = 0;
int emptyMax = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) {
int count = 0;
int emptyCnt = 0;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n)) {
for (int p : pref) {
if (p == map[nx][ny]) {
count++;
}
}
if (map[nx][ny] == 0) {
emptyCnt++;
}
}
}
if (count > prefMax) {
prefMax = count;
emptyMax = emptyCnt;
x = i;
y = j;
}
if (count == prefMax && emptyCnt > emptyMax) {
emptyMax = emptyCnt;
x = i;
y = j;
}
}
}
}
if(x != -1 && y != -1)
map[x][y] = cur;
}이렇게 구현을 하면 예제는 문제에서 주어진 예제는 통과가 가능하다. 하지만 제출을 한다면 틀리게 될 것이다.
문제는 지금 들어오는 학생이 현재 자리하고 있는 학생들 모두와 선호하고 있지 않다면 위치를 찾아주지 못한다는 것이다.
그래서 여러가지 생각을 하고 조건을 추가하려 했지만 문제 특성상 if-else 구문이 많아져 오히려 디버깅하는데 어려움이 있었다.
그래서 그냥 n도 작고해서 교실의 빈자리의 모든 값을 저장했다. (x,y)뿐만 아니라 주변 빈 자리수와, 주변 선호하는 학생의 수를 모두 리스트로 저장하여
comparator를 문제의 조건에 맞게 구현한 후 정렬하여 가장 처음 나오는 값의 (x,y)에 학생을 배치하는 형태로 변경했다.
아마 그냥 조건을 달아서 답을 구하는 방법보다는 시간복잡도가 증가할 것이다.(정렬이 들어가기 때문)
하지만 n이 충분히 작고 풀이에 있어 정확도가 올라가고 디버깅이 용이할 것이라 생각되어 이렇게 코드를 작성했고 정답을 얻을 수 있었다.
예상 시간 복잡도로는 쌍을 저장하는 list를 정렬하는데 nlogn이고 교실의 최대 빈 자리의 개수가 n^2 - 1이기 때문에 아마 n^3logn으로 예상된다.
코드
import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
public class Main {
static int[] dx = {-1, 0, 0, 1};
static int[] dy = {0, -1, 1, 0};
static int[][] map;
static int n;
static ArrayList<Pair> pairs;
static Comparator<Pair> comp;
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
int pNum = n * n;
map = new int[n][n];
int[] entry = new int[pNum];
int[][] pref = new int[pNum + 1][4];
pairs = new ArrayList<>();
comp = new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
if(o1.prefCnt > o2.prefCnt)
return -1;
else if(o1.prefCnt == o2.prefCnt) {
if(o1.emptyCnt > o2.emptyCnt) {
return -1;
}
else if(o1.emptyCnt == o2.emptyCnt) {
if(o1.x < o2.x) {
return -1;
}
else if(o1.x == o2.x) {
if(o1.y < o2.y) {
return -1;
}
else if(o1.y > o2.y)
return 1;
else
return 0;
}
else
return 1;
}
else
return 1;
}
else
return 1;
}
};
for (int i = 0; i < pNum; i++) {
String[] line = br.readLine().split(" ");
int idx = Integer.parseInt(line[0]);
entry[i] = idx;
for (int j = 1; j < line.length; j++) {
pref[idx][j - 1] = Integer.parseInt(line[j]);
}
}
for (int i = 0; i < pNum; i++) {
if (i == 0) {
map[1][1] = entry[i];
} else {
findPos(pref[entry[i]], entry[i]);
}
}
int answer = getScore(pref);
bw.write(answer + "\n");
bw.close();
br.close();
}
private static void findPos(int[] pref, int cur) {
pairs.clear();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) {
int count = 0;
int emptyCnt = 0;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n)) {
for (int p : pref) {
if (p == map[nx][ny]) {
count++;
}
}
if (map[nx][ny] == 0) {
emptyCnt++;
}
}
}
pairs.add(new Pair(i,j,count, emptyCnt));
}
}
}
pairs.sort(comp);
Pair p = pairs.get(0);
map[p.x][p.y] = cur;
}
private static int getScore(int[][] pref) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int count = 0;
int[] list = pref[map[i][j]];
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n)) {
for (int a : list) {
if (a == map[nx][ny]) {
count++;
break;
}
}
}
}
if (count == 0)
sum += 0;
else if (count == 1)
sum += 1;
else if (count == 2)
sum += 10;
else if (count == 3)
sum += 100;
else if (count == 4)
sum += 1000;
}
}
return sum;
}
}
class Pair {
public int x;
public int y;
public int prefCnt;
public int emptyCnt;
public Pair(int x, int y, int prefCnt, int emptyCnt) {
this.x = x;
this.y = y;
this.prefCnt = prefCnt;
this.emptyCnt = emptyCnt;
}
}