백준 상어 초등학교

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 N이 주어진다.
둘째 줄부터 N^2개의 줄에 학생의 번호와 그 학생이 좋아하는 학생 4명의 번호가 한 줄에 하나씩 선생님이 자리를 정할 순서대로 주어진다.
학생의 번호는 중복되지 않으며, 어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다.
입력으로 주어지는 학생의 번호, 좋아하는 학생의 번호는 N2보다 작거나 같은 자연수이다.
어떤 학생이 자기 자신을 좋아하는 경우는 없다.

첫째 줄에 학생의 만족도의 총 합을 출력한다.

내가 이 문제를 보고 생각해본 부분

classroom 2차원 배열로 자리 배치를 나타내며, 0은 빈 자리이다.
favorites 맵은 각 학생 번호마다 좋아하는 학생 번호 리스트를 저장한다.
먼저 입력받은 학생 순서대로 한 명씩 seatStudent() 메서드를 통하여 최적의 자리를 찾고 배치한다.
자리 선정 조건을 모두 비교하여 최적 조건을 가진 자리를 선택한다.
좋아하는 학생 인접 수 최대
빈 칸 인접 수 최대
행, 열 번호 오름차순으로 우선순위 결정
모든 학생 배치가 끝나면 calculateSatisfaction()로 총 만족도를 계산한다.
각 학생에 대해 인접한 칸에 몇 명 좋아하는 학생이 있는지를 세고 점수를 합산한다.

코드로 구현

package baekjoon.baekjoon_33;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 백준 21608번 문제
public class Main1343 {
    static int N;
    static int[][] classroom;
    static Map<Integer, List<Integer>> favorites = new HashMap<>();
    // 상하좌우 방향
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        classroom = new int[N][N];
        int totalStudents = N * N;
        int[] order = new int[totalStudents]; // 학생 배정 순서
        for (int i = 0; i < totalStudents; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int student = Integer.parseInt(st.nextToken());
            order[i] = student;
            List<Integer> favList = new ArrayList<>();
            for (int j = 0; j < 4; j++) {
                favList.add(Integer.parseInt(st.nextToken()));
            }
            favorites.put(student, favList);
        }

        for (int i = 0; i < totalStudents; i++) {
            seatStudent(order[i]);
        }

        int satisfactionSum = calculateSatisfaction();
        System.out.println(satisfactionSum);
        br.close();
    }

    // 학생 자리 정하기
    static void seatStudent(int student) {
        int maxLikeCount = -1;
        int maxEmptyCount = -1;
        int selectedRow = -1;
        int selectedCol = -1;

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (classroom[r][c] != 0)
                    continue; // 이미 자리 찼으면 skip

                int likeCount = 0; // 좋아하는 학생 인접 수
                int emptyCount = 0; // 빈 인접 칸 수

                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N)
                        continue;

                    if (classroom[nr][nc] == 0) {
                        emptyCount++;
                    } else if (favorites.get(student).contains(classroom[nr][nc])) {
                        likeCount++;
                    }
                }

                // 조건 비교
                if (likeCount > maxLikeCount ||
                        (likeCount == maxLikeCount && emptyCount > maxEmptyCount) ||
                        (likeCount == maxLikeCount && emptyCount == maxEmptyCount && (selectedRow == -1 || r < selectedRow)) ||
                        (likeCount == maxLikeCount && emptyCount == maxEmptyCount && r == selectedRow && c < selectedCol)) {
                    maxLikeCount = likeCount;
                    maxEmptyCount = emptyCount;
                    selectedRow = r;
                    selectedCol = c;
                }
            }
        }
        classroom[selectedRow][selectedCol] = student;
    }

    // 만족도 계산
    static int calculateSatisfaction() {
        int sum = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int student = classroom[r][c];
                int likeCount = 0;
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N)
                        continue;
                    if (favorites.get(student).contains(classroom[nr][nc])) {
                        likeCount++;
                    }
                }
                // 만족도 점수 규칙
                if (likeCount == 1)
                    sum += 1;
                else if (likeCount == 2)
                    sum += 10;
                else if (likeCount == 3)
                    sum += 100;
                else if (likeCount == 4)
                    sum += 1000;
            }
        }
        return sum;
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.