백준(BOJ) 21608 : 상어 초등학교

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

 

문제 자체는 어렵지 않은데 까다로운 설정들이 들어가있어서 다시 해볼때도 주의하면서 해보는게 좋다.

 

🚀풀이

사방탐색, HashMap, 구현력

앉을 좌석을 찾는 방법을 구현할 때 NxN 배열을 순차 탐색하며 주어진 조건 3가지를 고려하여 자리를 선택하여

차례대로 학생들을 배치하였다.

3가지 조건을 고려하기 용이하도록 Seat 클래스를 만든 뒤, Comparable 인터 페이스를 상속하여 비교하였다.

비교하기 용이하기 위해 Seat클래스에는 x y 좌표, 주변 좋아하는 학생 수, 주변 빈칸 수를 필드로 가지도록 하였다.

 

Seat 클래스안에 정보들을 한 번에 가지고 있지 않았더라면 중첩 if 문들로 비교를 해야 해서 가독성이 많이 떨어질 것이므로  주변에 내가 좋아하는 친구의 명수, 주변의 빈자리수에 관한 정보를 갖는 것이 좋다.

좌석을 비교할 때 인접 좋아하는 학생 수, 인접 빈칸 수를 알아야 하므로

getStudnetSum( ) 함수와 getEmptySum( ) 함수를 만들어 사용하였다.

getStudnetSum( ) 함수는 차후에 점수 합산할 때도 재사용할 수 있었다.

각 학생마다 좋아하는 학생들을 저장하기위해 Map<Integer, Set<Integer>> 을 사용하여 정보를 저장했다.

Map의 value가 Set인 이유는 좌석을 찾을때 주변에 좋아하는 사람이 있는지를 contains( ) 함수로 빠르게 판단하기 위해 사용했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

class Seat implements Comparable<Seat> {
    int y;
    int x;
    int adjacentBestFriends;
    int adjacentVacantSeat;

    public Seat(int y, int x, int adjacentBestFriends, int adjacentVacantSeat) {
        this.y = y;
        this.x = x;
        this.adjacentBestFriends = adjacentBestFriends;
        this.adjacentVacantSeat = adjacentVacantSeat;
    }

    @Override
    public int compareTo(Seat o) {
        if (adjacentBestFriends != o.adjacentBestFriends)
            return -(adjacentBestFriends - o.adjacentBestFriends);
        if (adjacentVacantSeat != o.adjacentVacantSeat)
            return -(adjacentVacantSeat - o.adjacentVacantSeat);
        if (y != o.y)
            return y - o.y;
        return x - o.x;
    }
}

public class Main {
    public static Seat findSeat(int[][] result, int student, Map<Integer, Set<Integer>> preferencies, int[] yDirection, int[] xDirection) {
        int length = result[0].length;
        Seat seat = null;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (result[i][j] > 0)
                    continue;
                Seat cur = new Seat(i, j, getAdjacentBF(i, j, student, preferencies, yDirection, xDirection, result), getAdjacentES(i, j, result, yDirection, xDirection));
                if (seat == null) {
                    seat = cur;
                    continue;
                }
                if (seat.compareTo(cur) > 0) {
                    seat = cur;
                }
            }
        }
        return seat;
    }

    public static int getAdjacentBF(int i, int j, int student, Map<Integer, Set<Integer>> preferencies, int[] yDirection, int[] xDirection, int[][] result) {
        int length = result[0].length;
        int output = 0;
        for (int k = 0; k < 4; k++) {
            int ny = i + yDirection[k];
            int nx = j + xDirection[k];
            if (ny < 0 || ny >= length || nx < 0 || nx >= length)
                continue;
            if (preferencies.get(student).contains(result[ny][nx]))
                output++;
        }
        return output;
    }

    public static int getAdjacentES(int i, int j, int[][] result, int[] yDirection, int[] xDirection) {
        int length = result.length;
        int output = 0;
        for (int k = 0; k < 4; k++) {
            int ny = i + yDirection[k];
            int nx = j + xDirection[k];
            if (ny < 0 || ny >= length || nx < 0 || nx >= length)
                continue;
            if (result[ny][nx] == 0)
                output++;
        }
        return output;
    }

    public static void solution(int n, int[] students, Map<Integer, Set<Integer>> preferencies) {
        int[][] result = new int[n][n];
        int[] yDirection = {-1, 1, 0, 0};
        int[] xDirection = {0, 0, -1, 1};

        for (int i = 0; i < students.length; i++) {

            Seat seat = findSeat(result, students[i], preferencies, yDirection, xDirection);
            result[seat.y][seat.x] = students[i];
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int value = getAdjacentBF(i, j, result[i][j], preferencies, yDirection, xDirection, result);
                if (value > 0)
                    answer += (int) Math.pow(10, value - 1);
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        Map<Integer, Set<Integer>> preferencies = new HashMap<>();
        int[] students = new int[num * num];
        StringTokenizer st;
        for (int i = 0; i < num * num; i++) {
            st = new StringTokenizer(br.readLine());
            students[i] = Integer.parseInt(st.nextToken());
            preferencies.put(students[i], new HashSet<Integer>());
            for (int j = 0; j < 4; j++)
                preferencies.get(students[i]).add(Integer.parseInt(st.nextToken()));
        }
        solution(num, students, preferencies);
    }
}