[JAVA] 백준 q21608 - 상어 초등학교

21608번: 상어 초등학교

---

의식의 흐름

빡구현,...

 

풀이 과정

1. 교실 크기(N)를 입력받는다.
2. 각 학생의 자리를 찾는다.
2-1) 학생 번호(studentNum), 좋아하는 학생들의 번호(favorites[studentNum])을 입력받는다.
2-2) 학생들의 자리를 지정한 배열(seat)을 이용하여 각 자리 정보(Seat)를 ArrayList(possibleSeats)에 저장한다.

자리 정보(Seat)는 'x좌표, y좌표, 근처 빈자리 개수, 근처 좋아하는 학생 수'를 담고 있다.

2-3) possibleSeats를 문제 조건에 맞게 정렬한다.

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

2-4) possibleSeats.get(0)에 해당하는 자리가 최적의 자리이므로 seat 배열의 possibleSeats.get(0)에 해당하는 자리에 studentNum을 저장한다.
3. 학생들의 만족도 합(score)을 구한다.
3-1) seat 배열을 돌며 주변 좋아하는 학생 수(favoriteCnt)를 구한다.
3-2) favoriteCnt에 따라 해당하는 만족도를 score에 더한다.

if(favoriteCnt == 1){
    score += 1;
}
else if(favoriteCnt == 2){
    score += 10;
}
else if(favoriteCnt == 3){
    score += 100;
}
else if(favoriteCnt == 4){
    score += 1000;
}

4. score를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[][] seat;
    public static ArrayList<Integer> seatedStudents;
    public static ArrayList<Integer>[] favorites;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,1,-1};
    public static int score = 0;

    public static class Seat implements Comparable<Seat> {
        int x;
        int y;
        int blankCnt;
        int favoriteCnt;

        public Seat(int x, int y, int blankCnt, int favoriteCnt){
            this.x = x;
            this.y = y;
            this.blankCnt = blankCnt;
            this.favoriteCnt = favoriteCnt;
        }

        @Override
        public int compareTo(Seat o) {
            if(o.favoriteCnt != this.favoriteCnt){
                return o.favoriteCnt - this.favoriteCnt;
            }

            if(o.blankCnt != this.blankCnt){
                return o.blankCnt - this.blankCnt;
            }

            if(o.x != this.x){
                return this.x - o.x;
            }

            return this.y - o.y;
        }
    }

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

        N = Integer.parseInt(br.readLine());
        seat = new int[N+1][N+1];
        seatedStudents = new ArrayList<>();
        favorites = new ArrayList[N*N+1];

        for(int i=0;i<N*N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int studentNum = Integer.parseInt(st.nextToken());
            favorites[studentNum] = new ArrayList<>();
            for(int j=0;j<4;j++){
                int favoriteStudent = Integer.parseInt(st.nextToken());
                favorites[studentNum].add(favoriteStudent);
            }

            findSeat(studentNum);
            seatedStudents.add(studentNum);
        }

        caculateScore();
        bw.write(Integer.toString(score));

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

    public static void findSeat(int studentNum){
        ArrayList<Seat> possibleSeats = new ArrayList<>();

        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(seat[i][j] != 0){
                    continue;
                }

                int blankCnt = 0;
                int favoriteCnt = 0;

                for(int k=0;k<4;k++){
                    int newX = i + dx[k];
                    int newY = j + dy[k];

                    if(newX < 1 || newX > N || newY < 1 || newY > N){
                        continue;
                    }

                    if(seat[newX][newY] == 0){
                        blankCnt++;
                    }
                    else if(favorites[studentNum].contains(seat[newX][newY])){
                        favoriteCnt++;
                    }
                }
                possibleSeats.add(new Seat(i, j, blankCnt, favoriteCnt));
            }
        }

        Collections.sort(possibleSeats);
        Seat finalSeat = possibleSeats.get(0);
        seat[finalSeat.x][finalSeat.y] = studentNum;
    }

    public static void caculateScore(){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                int favoriteCnt = 0;

                for(int k=0;k<4;k++){
                    int newX = i + dx[k];
                    int newY = j + dy[k];

                    if(newX < 1 || newX > N || newY < 1 || newY > N){
                        continue;
                    }

                    if(favorites[seat[i][j]].contains(seat[newX][newY])){
                        favoriteCnt++;
                    }
                }

                if(favoriteCnt == 1){
                    score += 1;
                }
                else if(favoriteCnt == 2){
                    score += 10;
                }
                else if(favoriteCnt == 3){
                    score += 100;
                }
                else if(favoriteCnt == 4){
                    score += 1000;
                }
            }
        }
    }
}