[backjoon]21608 상어초등학교 java

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

21608번: 상어 초등학교

삼성전자 21 상반기 ce/im 기출문제

요구 사항대로 하면 되는 문제인데 조건들이 너무 세분화되어있어서 까다롭다고 느꼈다.

나무 재테크랑 비슷한 유형이라고 생각된다.

이 문제는 기본적으로 구현해야할 부분이 4단계이다. 근데 하나하나 유기적으로 연결되어 있어서 예외처리를 주의해줘야한다.

친구들 정보를 입력받는데, 친구들 입력 정보들은 마지막에 좋아하는 학생들이 주변에 얼마나 있는지 확인해줘야하기 때문에 친구들을 저장해줄 Set 배열을 만들어주고 친구들을 배열에 넣어준다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.

-> 이 과정에서 불필요한 탐색을 안 하기 위해 배열을 이용해서 null 인 경우 탐색을 안 하도록 했다.(curSeat)

-> 나의 경우엔 친구들 주변을 모두 탐색하여 빈 자리들을 모두 카운트하여 가장 큰 값을 Queue에 담아주고, Queue에서 빼내었다. (Queue도 필요없고 그냥 list여도 된다.)

2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.

-> 만족하는 칸들을 기준으로 1과 같이 빈 칸이 가장 많은 곳을 탐색한다.

3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

-> 우선순위큐나 정렬을 이용한다. (삼성 문제에서 이런 부분이 나온다면 꼭 정렬을 사용해야한다.)

 

나의 경우 4방향 탐색이 bfs 방식이 너무 익숙해서 Queue를 이용했는데 저런 방식보다 그냥 list를 이용해도 될 것 같다.

후보군들을 구할 때 절대로 자리가 있는 곳들은 넣지 않도록 유의한다.

또한 값이 1부터 시작하기 때문에 런타임에러가 뜨기도 쉽다.

 

import java.io.*;
import java.util.*;
 
/**
 **/
class Main {
    static int N;
    static int[][] map;
    static Dot[] curSeat;
    static boolean[][] marked;
    static int[][] dirs = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        curSeat = new Dot[N * N];
        map = new int[N][N];
 
        marked = new boolean[N][N];
        Set<Integer>[] satis = new Set[N * N];
        for (int i = 0; i < N * N; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()) - 1;
            int[] friends = new int[4];
            satis[n] = new HashSet<>();
            for (int j = 0; j < 4; j++) {
                friends[j] = Integer.parseInt(st.nextToken()) - 1;
                satis[n].add(friends[j]);
            }
            Queue<Dot> seat = step1(n, friends);
            if (seat.size() == 1) {
                Dot last = seat.poll();
                map[last.row][last.col] = n;
                marked[last.row][last.col] = true;
                curSeat[n] = last;
                continue;
            } else {
                seat = step2(seat);
                if (seat.size() == 1) {
                    Dot last = seat.poll();
                    map[last.row][last.col] = n;
                    curSeat[n] = last;
                    marked[last.row][last.col] = true;
                    continue;
                } else {
                    PriorityQueue<Dot> pq = new PriorityQueue<>();
                    
                    while (!seat.isEmpty())
                        pq.add(seat.poll());
                    
                    Dot last = pq.poll();
                    map[last.row][last.col] = n;
                    curSeat[n] = last;
                    marked[last.row][last.col] = true;
                }
            }
 
        }
        System.out.println(cal(satis));
    }
 
    public static int cal(Set[] satis) {
        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int cur = map[i][j];
                Set set = satis[cur];
                int cnt = 0;
                for (int d = 0; d < 4; d++) {
                    int nextR = i + dirs[d][0];
                    int nextC = j + dirs[d][1];
 
                    if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N)
                        continue;
                    int result = map[nextR][nextC];
                    if (set.contains(result))
                        cnt++;
 
                }
                if (cnt == 0)
                    answer += 0;
                else if (cnt == 1)
                    answer += 1;
                else if (cnt == 2)
                    answer += 10;
                else if (cnt == 3)
                    answer += 100;
                else if (cnt == 4)
                    answer += 1000;
            }
        }
 
        return answer;
    }
 
    public static Queue<Dot> step2(Queue<Dot> cur) {
        Queue<Dot> temp = new LinkedList<>();
 
        int[][] empty = new int[N][N];
 
        int max = Integer.MIN_VALUE;
        while (!cur.isEmpty()) {
            int cnt = 0;
            Dot curDot = cur.poll();
            for (int d = 0; d < 4; d++) {
                int nextR = curDot.row + dirs[d][0];
                int nextC = curDot.col + dirs[d][1];
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N)
                    continue;
                if (marked[nextR][nextC])
                    continue;
                cnt++;
            }
            empty[curDot.row][curDot.col] = cnt;
            max = Math.max(max, cnt);
            temp.add(curDot);
        }
 
        while (!temp.isEmpty()) {
            Dot curDot = temp.poll();
            int cnt = empty[curDot.row][curDot.col];
            if (cnt == max && !marked[curDot.row][curDot.col])
                cur.add(curDot);
        }
 
        return cur;
    }
 
    public static Queue<Dot> step1(int n, int[] friends) {
        Queue<Dot> result = new LinkedList<>();
        int[][] close = new int[N][N];
        int max = 0;
        for (int x : friends) {
            if (curSeat[x] == null)
                continue;
            for (int d = 0; d < 4; d++) {
                int nextR = curSeat[x].row + dirs[d][0];
                int nextC = curSeat[x].col + dirs[d][1];
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N)
                    continue;
                if (marked[nextR][nextC])
                    continue;
                close[nextR][nextC]++;
                max = Math.max(max, close[nextR][nextC]);
            }
        }
 
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (close[r][c] == max && !marked[r][c])
                    result.add(new Dot(r, c));
            }
        }
 
        return result;
    }
}
 
class Dot implements Comparable<Dot> {
    int row;
    int col;
 
    Dot(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
    @Override
    public int compareTo(Dot o) {
        // TODO Auto-generated method stub
        if (this.row == o.row)
            return this.col - o.col;
        return this.row - o.row;
    }
}