상어 초등학교

📍 문제 설명

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

21608번: 상어 초등학교

 

💡 접근

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

이 3가지 조건을 알맞게 구현하면 되는 문제

해당 학생의 좋아하는 학생 수 / 비어있는 칸의 수가 필요하다.

 

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, r, answer, cnt, sum, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, firstX, firstY;
    static int[] arr, dx = {1,0,-1,0}, dy = {0,-1,0,1};
    static long[] dp;
    static int[][] board, clone, nearEmptySeatCnt;
    static boolean[][] visited;
    static ArrayList<Integer> list;
    static HashMap<Integer, ArrayList> map;
    static TreeSet<Character> set;
    static StringBuilder sb;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        map = new HashMap<>();

        //비어있는 칸 계산
        findNearEmptySeat();

        for(int tc = 0; tc < n * n; tc++) {
            st = new StringTokenizer(br.readLine());
            list = new ArrayList<>();
            int num = Integer.valueOf(st.nextToken());
            for(int i = 0; i < 4; i++) {
                list.add(Integer.valueOf(st.nextToken()));
            }
            //만족도 계산시 사용
            map.put(num, list);
            //앉을 자리 찾기
            findSeat(num);

        }

        //만족도 계산
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cnt = 0;
                for(int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx < 0|| ny < 0 || ny >= n || nx >= n) continue;
                    if(map.get(board[i][j]).contains(board[nx][ny])) cnt++;
                }
                if(cnt==1) sum+=1;
                else if(cnt==2) sum+=10;
                else if(cnt==3) sum+=100;
                else if(cnt==4) sum+=1000;
            }
        }
        System.out.println(sum);
    }

    private static void findSeat(int num) {
        int[][] nearFriendCnt = new int[n][n];
        //빈 칸중 상하좌우 확인하여 좋아하는 학생 수 넣기
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 0) {
                    for(int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
                        //다음칸이 자기가 좋아하는 친구면 증가시켜줘
                        if(list.contains(board[nx][ny])) {
                            nearFriendCnt[i][j]++;
                        }
                    }
                }
            }
        }

        //좋아하는 학생이 많고, 비어있는 칸이 가장 많은 칸으로 자리 정하기
        int emptyCntMax = 0;
        int nearFriendCntMax = 0;
        int targetX = 0;
        int targetY = 0;

        for(int i=0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] != 0) continue;
                //좋아하는 학생 최댓값보다 현재값이 크면
                //좋아하는 학생 최댓값 비어있는 칸의 최댓값 갱신해주기
                if(nearFriendCntMax < nearFriendCnt[i][j]) {
                    targetX = i;
                    targetY = j;
                    nearFriendCntMax = nearFriendCnt[i][j];
                    emptyCntMax = nearEmptySeatCnt[i][j];
                }
                //좋아하는 학생 수가 같으나 비어있는 칸이 더 크면
                //그 자리로 자리를 정하기
                //비어있는 칸이 여러 칸일 경우 '<' 조건에 의해 제일 작은 칸이 자리가 됨
                else if(nearFriendCntMax == nearFriendCnt[i][j] && emptyCntMax < nearEmptySeatCnt[i][j]) {
                    emptyCntMax = nearEmptySeatCnt[i][j];
                    targetX = i;
                    targetY = j;
                }
            }
        }

        //정한 자리로가서 앉기
        board[targetX][targetY] = num;

        //현재 칸의 인접한 방향의 비어있는 칸을 줄여주기
        for(int i=0; i<4; i++) {
            int nx = targetX + dx[i];
            int ny = targetY + dy[i];
            if(nx<0 || ny<0 || nx>=n || ny>=n || board[nx][ny] != 0) continue;
            nearEmptySeatCnt[nx][ny]--;
        }
    }

    private static void findNearEmptySeat() {
        nearEmptySeatCnt = new int[n][n];

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                int cnt = 4;
                if(i == 0 || i == n-1) cnt--;
                if(j == 0 || j == n-1) cnt--;
                nearEmptySeatCnt[i][j] = cnt;
            }
        }
    }
    private void solution() {

    }


}