[JAVA]백준 21608번 상어 초등학교

📌문제 링크

---

https://www.acmicpc.net/problem/21608

📌문제 설명

---

N의 크기가 굉장히 작기 때문에 최적화를 신경쓰지 않고 그냥 흐름대로 구현하면 됩니다. 우선순위 큐를 사용해서 문제의 조건을 정렬 하나로 해결했습니다.

📌코드

---

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

// 학생 정보를 저장하는 클래스
class Student {
    int idx, f1, f2, f3, f4; // 학생 번호와 좋아하는 학생 4명

    public Student(int idx, int f1, int f2, int f3, int f4) {
        this.idx = idx;
        this.f1 = f1;
        this.f2 = f2;
        this.f3 = f3;
        this.f4 = f4;
    }
}

// 좌표를 저장하는 클래스
class Pair {
    int x, y; // 행과 열

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

// 자리 배치 정보를 저장하고 비교하는 클래스
class Comp implements Comparable<Comp> {
    int x, y, favoriteCnt, emptyCnt; // 좌표(x, y), 좋아하는 학생 수, 빈 칸 수

    public Comp(int x, int y, int favoriteCnt, int emptyCnt) {
        this.x = x;
        this.y = y;
        this.favoriteCnt = favoriteCnt;
        this.emptyCnt = emptyCnt;
    }

    @Override
    public int compareTo(Comp o) {
        if (this.favoriteCnt != o.favoriteCnt) return o.favoriteCnt - this.favoriteCnt;
        if (this.emptyCnt != o.emptyCnt) return o.emptyCnt - this.emptyCnt;
        if (this.x != o.x) return this.x - o.x;
        return this.y - o.y;
    }
}

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static int N;
    static List<Student> students = new ArrayList<>();
    static int[][] map;
    static int[] dx = {0, 0, 1, -1}; // 상하좌우 이동
    static int[] dy = {1, -1, 0, 0};

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

        input(); // 입력 처리
        solve(); // 문제 해결

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

    // 입력 처리
    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine()); // 교실 크기 입력
        map = new int[N + 1][N + 1]; // 1-based index

        for (int i = 0; i < N * N; i++) { // N^2개의 학생 정보 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            int f1 = Integer.parseInt(st.nextToken());
            int f2 = Integer.parseInt(st.nextToken());
            int f3 = Integer.parseInt(st.nextToken());
            int f4 = Integer.parseInt(st.nextToken());
            students.add(new Student(idx, f1, f2, f3, f4));
        }
    }

    // 학생 자리 배치
    public static void assignSeat(Student student) {
        PriorityQueue<Comp> pq = new PriorityQueue<>();

        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {
                if (map[x][y] != 0) continue; // 이미 배정된 자리라면 건너뜀

                int favoriteCnt = 0, emptyCnt = 0;
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if (nx < 1 || ny < 1 || nx > N || ny > N) continue;

                    if (map[nx][ny] == student.f1 || map[nx][ny] == student.f2 ||
                            map[nx][ny] == student.f3 || map[nx][ny] == student.f4) {
                        favoriteCnt++;
                    }
                    if (map[nx][ny] == 0) {
                        emptyCnt++;
                    }
                }
                pq.add(new Comp(x, y, favoriteCnt, emptyCnt));
            }
        }

        if (!pq.isEmpty()) {
            Comp bestSeat = pq.poll();
            map[bestSeat.x][bestSeat.y] = student.idx;
        }
    }

    // 학생의 만족도 계산
    public static int calculateSatisfaction() {
        int totalSatisfaction = 0;

        for (Student student : students) {
            Pair loc = findStudentLocation(student);
            int x = loc.x, y = loc.y;
            int count = 0;

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 1 || ny < 1 || nx > N || ny > N) continue;

                if (map[nx][ny] == student.f1 || map[nx][ny] == student.f2 ||
                        map[nx][ny] == student.f3 || map[nx][ny] == student.f4) {
                    count++;
                }
            }

            if (count == 1) totalSatisfaction += 1;
            else if (count == 2) totalSatisfaction += 10;
            else if (count == 3) totalSatisfaction += 100;
            else if (count == 4) totalSatisfaction += 1000;
        }

        return totalSatisfaction;
    }

    // 학생의 위치 찾기
    public static Pair findStudentLocation(Student student) {
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {
                if (map[x][y] == student.idx) {
                    return new Pair(x, y);
                }
            }
        }
        return null; // 이론상 실행되지 않음
    }

    // 문제 해결
    public static void solve() throws Exception {
        for (Student student : students) {
            assignSeat(student);
        }

        int satisfaction = calculateSatisfaction();
        bw.write(satisfaction + "\n");
        bw.flush();
    }
}