백준 - 21808 상어 초등학교(Java)

구현 문제입니다.

 

n*n 의 교실에 학생들을 특정 방식으로 채울 때의 만족도를 구하는 문제입니다.

특정 방식은 세 가지 절차가 주어집니다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

인접의 조건은 |r1 - r2| + |c1 - c2| = 1 이기 때문에, 상하좌우를 확인하면 됩니다.

 

문제의 입력 첫 번째 줄에는 n이 주어집니다.

그리고, 두 번째 줄부터 n*n 만큼의 좋아하는 친구(연결 관계)가 주어집니다.

 

첫 번째 "비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다." 조건의 구현 방법은 다음과 같습니다.

• 좋아하는 친구가 앉아있을 때, 인접한 위치(상하좌우)의 값을 증가한다. (값을 저장할 별도의 배열 필요)
• 증가된 값의 최대를 구한다.

 

두 번째 "1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다." 조건의 구현 방법은 다음과 같습니다.

• 1번에 의해 구해진 최대 값이 여러 개 일 경우, 해당 위치들의 인접한 공백 개수를 구한다.
• 공백의 최대를 구한다.

 

세 번째 "2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다." 조건의 구현 방법은 다음과 같습니다.

• 행과 열을 기준으로 오름차순 정렬한다.
• 정렬된 값에서 첫 번째의 값을 구해 만족도를 계산한다.

 

[구현 코드]

import java.io.*;
import java.util.*;

public class Main {
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};
    private static final String SEPARATOR = " ";

    private static List<Integer> order; // 각 입력의 첫 번째
    private static List<List<Integer>> relations; // 각 학생들이 좋아하는 친구들(연결관계)
    private static Map<Integer, int[]> seat; // 배정된 학생들의 좌석 위치
    private static int[][] classroom; // 배정된 학생들 저장

    private static int n, nn;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        init(br);

        for (int i = 0; i < nn; i++) {
            int person = order.get(i);

            // 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
            List<int[]> firstCondition = new ArrayList<>();
            int[][] nearFriends = new int[n][n];
            int maxNearFriendCount = getMaxNearFriendCount(person, nearFriends);

            for (int r = 0; r < n; r++) {
                for (int t = 0; t < n; t++) {
                    // 친구 근처의 비어있는 자리가 없거나, 이미 배정된 친구가 없을 수 있음
                    if (nearFriends[r][t] == maxNearFriendCount && classroom[r][t] == -1) {
                        firstCondition.add(new int[]{r, t});
                    }
                }
            }

            // 1의 유일한 경우일 때
            if (firstCondition.size() == 1) {
                int x = firstCondition.get(0)[0];
                int y = firstCondition.get(0)[1];

                classroom[x][y] = person;
                seat.put(person, new int[]{x, y});
                continue;
            }

            // 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
            List<int[]> secondCondition = new ArrayList<>(firstCondition);
            int[][] blanks = new int[n][n];
            int maxBlanks = getMaxBlanks(secondCondition, blanks);

            List<int[]> thirdCondition = new ArrayList<>();
            for (int[] condition : secondCondition) {
                int cx = condition[0];
                int cy = condition[1];

                if (blanks[cx][cy] == maxBlanks && classroom[cx][cy] == -1) {
                    thirdCondition.add(condition);
                }
            }

            // 3. 2를 만족하는 칸도 여러 개인 경우에 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
            thirdCondition.sort((o1, o2) -> {
                if (o1[0] == o2[0]) return o1[1] - o2[1];
                return o1[0] - o2[0];
            });

            int x = thirdCondition.get(0)[0];
            int y = thirdCondition.get(0)[1];

            classroom[x][y] = person;
            seat.put(person, new int[]{x, y});
        }

        int answer = calculationSatisfaction(classroom, relations);

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static void init(BufferedReader br) throws IOException {
        n = Integer.parseInt(br.readLine());
        nn = n * n;

        order = new ArrayList<>();
        relations = new ArrayList<>();
        seat = new HashMap<>();
        classroom = new int[n][n];

        input(br);

        for (int i = 0; i < n; i++) {
            Arrays.fill(classroom[i], -1);
        }
    }

    private static void input(BufferedReader br) throws IOException {
        for (int i = 0; i < nn; i++) {
            relations.add(new ArrayList<>());
        }

        for (int i = 0; i < nn; i++) {
            StringTokenizer stz = new StringTokenizer(br.readLine(), SEPARATOR);

            int a = Integer.parseInt(stz.nextToken()) - 1;
            order.add(a);

            for (int j = 0; j < 4; j++) {
                int b = Integer.parseInt(stz.nextToken()) - 1;
                relations.get(a).add(b);
            }
        }
    }

    private static int getMaxNearFriendCount(int person, int[][] nearFriends) {
        int maxNearFriendCount = 0;
        for (int j = 0; j < 4; j++) {
            int likeFriend = relations.get(person).get(j);

            if (seat.containsKey(likeFriend)) { // 좋아하는 친구가 이미 좌석 배정이 끝났을 때.
                int cx = seat.get(likeFriend)[0];
                int cy = seat.get(likeFriend)[1];

                for (int d = 0; d < 4; d++) { // 인접 네 방향 확인
                    int nx = cx + dx[d];
                    int ny = cy + dy[d];

                    if (!inRange(nx, ny)) continue;
                    if (classroom[nx][ny] != -1) continue; // 비어있는지 확인

                    nearFriends[nx][ny] += 1;
                    maxNearFriendCount = Math.max(maxNearFriendCount, nearFriends[nx][ny]);
                }
            }
        }
        return maxNearFriendCount;
    }

    private static int getMaxBlanks(List<int[]> secondCondition, int[][] blanks) {
        int maxBlanks = 0;
        for (int[] condition : secondCondition) {
            int cx = condition[0];
            int cy = condition[1];

            // 인접한 칸 중에서 비어있는 칸의 개수를 셈
            int cnt = 0;
            for (int d = 0; d < 4; d++) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                if (!inRange(nx, ny)) continue;
                if (classroom[nx][ny] != -1) continue;

                cnt += 1;
            }

            blanks[cx][cy] = cnt;
            maxBlanks = Math.max(maxBlanks, cnt);
        }
        return maxBlanks;
    }

    private static boolean inRange(int x, int y) {
        return (x >= 0 && y >= 0 && x < n && y < n);
    }

    private static int calculationSatisfaction(int[][] classroom, List<List<Integer>> list) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int like = 0;
                int person = classroom[i][j];

                for (int d = 0; d < 4; d++) {
                    int nx = i + dx[d];
                    int ny = j + dy[d];

                    if (!inRange(nx, ny)) continue;

                    int near = classroom[nx][ny];
                    if (list.get(person).contains(near)) like++;
                }

                int satisfaction = (like == 0) ? 0 : (int) Math.pow(10, like - 1);
                sum += satisfaction;
            }
        }

        return sum;
    }
}