백준 21608번 <상어 초등학교>

백준 알고리즘 21608번

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

21608번: 상어 초등학교

---

21608번

상어 초등학교에 있는 교실은 N * N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N^2 명이다.

오늘은 모든 학생의 자리를 정하는 날인데, 자리를 정하는 순서는 정해져있고, 학생의 자리를 정하는 규칙은 다음과 같다.

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

자리를 모두 정한 후에 각 학생들의 만족도를 아래와 같이 구할 수 있는데 이 만족도의 총 합을 구하면 된다.

• 인접한 자리에 좋아하는 학생이 0명 있다면 만족도는 0이다.
• 인접한 자리에 좋아하는 학생이 1명 있다면 만족도는 1이다.
• 인접한 자리에 좋아하는 학생이 2명 있다면 만족도는 10이다.
• 인접한 자리에 좋아하는 학생이 3명 있다면 만족도는 100이다.
• 인접한 자리에 좋아하는 학생이 4명 있다면 만족도는 1000이다.

입력으로 첫 줄에 교실의 크기 N이 들어오고 그 다음 N^2개의 줄에 걸쳐 자리를 정하는 순서에 해당하는 학생의 번호와 그 학생이 좋아하는 4명의 친구가 들어온다.

 

출력으로 정해진 자리에 대한 만족도의 총 합을 출력하면 된다.

---

문제 해결

구현 문제!

문제를 구현하는데는 얼마 안걸렸는데 인덱스 처리 때문에 많은 시간을 썼다.

입력으로 들어오는 학생의 번호가 1부터 시작하고 코드 상에서는 0부터 시작하기 때문에 zero-index로 맞춰주었는데 그렇게 하면 문제가 있었다. 코드를 구현할 때, 0이면 비어있다고 판단했는데 학생의 번호가 0부터 시작하기 때문에 생기는 문제였다. 그래서 이번 문제에서는 코드 상에서 1번 학생부터 시작할 수 있도록 바꿔주었고 성공할 수 있었다.

 

구현한 함수는 다음과 같다.

answer()

• 모두 자리가 정해졌을 때, 인접한 자리에 좋아하는 친구가 몇 명인지 구한 후 만족도를 획득한다.

score(int cnt)

• cnt의 값을 좋아하는 친구의 수로 생각해 규칙에 맞는 만족도를 반환한다.

getPnt(int student)

• 비어있는 자리 중 규칙에 맞게 앉을 자리를 구한다.
• check 함수의 반환값이 true라면 현재 자리를 앉을 자리로 결정한다.

check(int likeCnt, int lCnt, int emptyCnt, int eCnt, int i, int j, int[] pnt)

• likeCnt, emptyCnt, pnt를 기준으로 삼아 자리를 정하는 규칙에 맞게 현재 위치를 변경해야 하는지 판단한다.
• likeCnt보다 lCnt가 크다면 true
• likeCnt보다 lCnt가 작다면 false
• emptyCnt보다 eCnt가 크다면 true
• emptyCnt보다 eCnt가 작다면 false
• pnt[0]보다 i가 크다면 true
• pnt[0]보다 i가 작다면 false
• pnt[1]보다 j가 크다면 true
• pnt[1]보다 j가 작다면 false

---

코드

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

public class BOJ_21608 {
    static int N, Ans;
    static int[] order;
    static int[][] ILike, room;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        order = new int[N * N + 1];         // order[i] : i번째에 앉는 학생 번호
        ILike = new int[N * N + 1][4];      // ILike[i] : i번 학생이 좋아하는 학생 4명
        room = new int[N][N];       // room[i][j] : (i, j)에 앉은 학생
        for (int i = 0; i < N*N; i++) {
            String[] inArr = br.readLine().split(" ");
            order[i] = Integer.parseInt(inArr[0]);
            for (int j = 1; j < 5; j++) {
                ILike[order[i]][j-1] = Integer.parseInt(inArr[j]);
            }
            Arrays.sort(ILike[i]);
        }   // end input

        for (int i = 0; i < N * N; i++) {   // 순서대로 정하기
            int[] pnt = getPnt(order[i]);
            room[pnt[0]][pnt[1]] = order[i];
        }

        System.out.println(answer());
    }
    static int answer() {
        int Ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int like = 0;
                for (int k = 0; k < 4; k++) {
                    int ni = i + di[k];
                    int nj = j + dj[k];
                    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
                    for (int p = 0; p < 4; p++) {
                        if (ILike[room[i][j]][p] == room[ni][nj]) {
                            like++;
                            break;
                        }
                    }
                }
                Ans += score(like);
            }
        }
        return Ans;
    }

    static int score(int cnt) {
        switch (cnt) {
            case 1:
                return 1;
            case 2:
                return 10;
            case 3:
                return 100;
            case 4:
                return 1000;
        }
        return 0;
    }

    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static int[] getPnt(int student) {
        int likeCnt = -1;
        int emptyCnt = -1;
        int[] pnt = {N, N};
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (room[i][j] != 0) continue;
                // 인접 위치 확인하기
                int lCnt = 0;
                int eCnt = 0;
                for (int k = 0; k < 4; k++) {
                    int ni = i + di[k];
                    int nj = j + dj[k];
                    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
                    if (room[ni][nj] == 0) {
                        eCnt++;
                        continue;
                    }
                    for (int p = 0; p < 4; p++) {
                        if (room[ni][nj] == ILike[student][p]) {
                            lCnt++;
                            break;
                        }
                    }
                }
                if (check(likeCnt, lCnt, emptyCnt, eCnt, i, j, pnt)) {
                    likeCnt = lCnt;
                    emptyCnt = eCnt;
                    pnt[0] = i;
                    pnt[1] = j;
                }
            }
        }
        return pnt;
    }

    static boolean check(int likeCnt, int lCnt, int emptyCnt, int eCnt, int i, int j, int[] pnt) {
        if (likeCnt < lCnt) return true;
        if (likeCnt > lCnt) return false;
        if (emptyCnt < eCnt) return true;
        if (emptyCnt > eCnt) return false;
        if (pnt[0] > i) return true;
        if (pnt[0] < i) return false;
        return pnt[1] > j;
    }
}

---

결과

---

4
4 1 2 5 7
12 1 4 5 9
2 1 3 4 12
5 4 8 11 15
10 2 4 11 13
1 2 3 4 5
16 1 4 5 8
7 4 5 9 10
11 5 9 14 16
9 2 7 11 13
6 2 7 14 16
13 7 9 10 15
8 7 9 13 15
14 2 4 9 11
3 4 5 12 16
15 5 7 13 16

78