백준 21608 (상어 초등학교) - java

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

21608번: 상어 초등학교

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

public class Main {
    static int[] dx = {0,0,-1,1}; // 인접한 칸
    static int[] dy = {1,-1,0,0};
    static int[][] board = new int[21][21]; // 학생 책상 좌표계
    static int n = 0;
    static Queue<student> q = new LinkedList<>(); // 학생 정보 큐
    static Queue<point> sq = new LinkedList<>(); // 만족도 측정에 사용할 큐

    static int result = 0; // 총 만족도
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());

        for(int i = 1;i<=n*n;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int num = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            q.add(new student(num,a,b,c,d));
        }

        where(); // 자리 배치

        score(); // 만족도 점수 측정
        System.out.println(result); // 총 만족도 출력

        br.close();
    }
    // 만족도 점수 측정
    static void score()
    {
        while(!sq.isEmpty())
        {
            point cur = sq.poll();
            int num = 0;
            for(int i=0;i<4;i++)
            {
                int nx = cur.x+dx[i];
                int ny = cur.y+dy[i];

                if(nx>=1&&nx<=n&&ny>=1&&ny<=n)
                {
                    if(board[nx][ny]==cur.like[0]||board[nx][ny]==cur.like[1]||board[nx][ny]==cur.like[2]||board[nx][ny]==cur.like[3])
                    {
                        num++; // 인접한 좌표에 좋아하는 학생의 수 조사
                    }
                }
            }
            
            /*학생의 수에 따른 점수 추가*/
            if(num==1)
            {
                result = result + 1;
            }
            else if(num==2)
            {
                result = result + 10;
            }
            else if(num==3)
            {
                result = result + 100;
            }
            else if(num==4)
            {
                result = result + 1000;
            }
        }
    }
    
    // 자리 배치하는 함수
    static void where()
    {
        while(!q.isEmpty())
        {
            student cur = q.poll();
            int like = 0; // 학생이 좋아하는 학생과 인접한 수
            int empty = 0; // 인접한 위치에 비어있는 자리의 수
            int nx = -1;
            int ny = -1;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    int tempty = 0; // 측정 비어있는 자리 수
                    int tlike = 0; // 측정 좋아하는 학생의 수
                    if(board[i][j]==0)
                    {
                        for(int k=0;k<4;k++)
                        {
                            int cx = i + dx[k]; // 인접한 자리의 좌표
                            int cy = j + dy[k];

                            if(cx>=1&&cx<=n&&cy>=1&&cy<=n)
                            {
                                if(board[cx][cy]==0) // 비어있다면
                                {
                                    tempty++;
                                }

                                else if(board[cx][cy]==cur.like[0]||board[cx][cy]==cur.like[1]||board[cx][cy]==cur.like[2]||board[cx][cy]==cur.like[3])
                                {
                                    tlike++; // 좋아하는 학생이라면
                                }
                            }
                        }
                        /*
                            우선순위
                            1. 좋아하는
                            2. 비어있는
                        */
                        if(tlike>like)
                        {
                            like = tlike;
                            empty = tempty;
                            nx = i;
                            ny = j;
                        }
                        else if(tlike==like)
                        {
                            if(tempty>empty)
                            {
                                like = tlike;
                                empty = tempty;
                                nx = i;
                                ny = j;
                            }
                        }
                    }
                }
            }
            // 위 조건에 만족하는 자리가 있다면
            if(nx!=-1&&ny!=-1)
            {
                board[nx][ny] = cur.num; // 자리 배치
                sq.add(new point(nx,ny,cur.like)); // 만족도 측정 큐에 추가
            }
            // 인접한 자리에 좋아하는 학생이나 비어있는 자리가 없는 경우 (낮은 행, 낮은 열 우선순위로 배치)
            else if(nx==-1&&ny==-1)
            {
                for1 : for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=n;j++)
                    {
                        if(board[i][j]==0)
                        {
                            board[i][j]=cur.num;
                            sq.add(new point(i,j,cur.like));
                            break for1; // 작은 행 , 작은 열 우선순위에 의해 자리를 찾은 경우 바로 반복문 종료
                        }
                    }
                }
            }

        }
    }
}
class student
{
    int num; // 학생의 번호
    int[] like = new int[4]; // 학생이 좋아하는 4명의 학생

    student(int num,int a,int b,int c,int d)
    {
        this.num = num;
        like[0] = a;
        like[1] = b;
        like[2] = c;
        like[3] = d;
    }
}

class point
{
    int x; // 학생의 행 좌표
    int y; // 학생의 열 좌표
    int[] like; // 학생이 좋아하는 4명의 학생

    point(int x,int y,int[] like)
    {
        this.x = x;
        this.y = y;
        this.like = like;
    }
}