백준 21608

🦈 백준 21608 : 상어 초등학교

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

21608번: 상어 초등학교

🦈 앞에서 풀었던 상어의 파이어볼보다 더 열받는 문제였다. 

🦈 문제 순서대로 구현하면 되는 문제이기는 하지만, 조건이 매우 복잡하여 틀린부분을 수정하는데 오래 걸렸다.

🦈 나는 아래  부분을 실수했었다. 

• 마지막 칸 하나만 남았을 때는 무조건 그 칸으로 들어갈 수 밖에 없다. 
• 방문 처리를 확실히 할 것. 학생 번호를 편의상 0부터 배치했더니, 이미 자리가 있는데 없다고 생각하고 덮어씌워지는 경우가 계속 발생하였다. 

🦈 이걸 제대로 카운트를 안하니깐 이미 앉아있는 자리를 빼앗는(...)다던가 아예 안 앉는 그런 불상사도 있었다.

🦈 그리고 학생 번호는 1부터 시작하다보니 처음에 0이면 학생이 배치되지 않은 좌석이라고 생각했는데, 내가 그냥 0부터 배치해서 이미 자리가 있는데도 덮어씌워지는 경우도 생겼다. 

---

🦈 주요 로직

🦈 좌석찾기 : findSeat

• 좋아하는 애가 많은 곳 찾기
  • 좋아하는 애들 중, 좌석이 배치된 애들이 있다면, 얘네 주변 4방향 좌석에 점수를 준다. 
  • 그리고 max를 구한다. 
  • 만약 max가 1개라면 얘가 바로 배치될 공간이고, 좋아하는 애들이 배치되지 않았거나, 여러 자리가 후보라면 빈칸 탐색 시작 

private static Pos findSeat(int index) {
    temp = new int[n][n];
    for (int s: likes[index]) {
        if (isSit[s] != null) {
            for (int i = 0; i < 4; i++) {
                int nextX = isSit[s].x + dirX[i];
                int nextY = isSit[s].y + dirY[i];

                if (!isValid(nextX, nextY)) {
                    continue;
                }

                if (map[nextX][nextY] != 0) {
                    continue;
                    // 이미 누가 앉아있다면 거긴 못앉으니까
                }
                temp[nextX][nextY]++;
            }
        }
    }

    ArrayList<Pos> posList = maxCount(findMax());
    Pos answer;
    if (posList.size() == 1) {
        answer = posList.get(0);
    }
    else {
        answer = findEmptyMax(posList);
    }
    return answer;
}

 

---

 

• 빈칸 많은 곳 찾기 : findEmptyMax를 findSeat에서 내부 호출 
  • 앞에서 후보들을 리스트 형태로 매개변수로 받아와서, 하나씩 검사한다.
  • 후보 리스트 만큼의 배열을 하나 만들고, 그 배열에 각 장소별 점수를 계산한다. 
  • 후보가 이미 차지된 경우도 있을 수 있는데, 이 경우에는 선택불가능하므로 -1로 점수를 넣고 continue처리 해줌. 
  • 그 뒤 max값을 찾는다. 
  • 그런데 이때, 모든 칸이 다 주변 빈칸이 0인 경우 (딱 한칸만 남아있다거나) 이런 경우에는 모든 칸 중 착석 안된 칸 밖에 못 앉히므로 그 칸이 자동으로 된다. 
  • max값이 다 똑같다면 가장 왼쪽 위에 있는 행이 정답이므로(문제의 조건에 따라) 가장 먼저 max가 나온 곳이 답이다. 

private static Pos findEmptyMax(ArrayList<Pos> posList) {
    int[] arr = new int[posList.size()];
    int max = -11;
    for (int i = 0; i < posList.size(); i++) {
        int count = 0;
        if (map[posList.get(i).x][posList.get(i).y] != 0) {
            arr[i]= -1;
            continue;
        }
        for (int j = 0; j < 4; j++) {
            int nextX = posList.get(i).x + dirX[j];
            int nextY = posList.get(i).y + dirY[j];

            if (!isValid(nextX, nextY)) {
                continue;
            }

            if (map[nextX][nextY] == 0) {
                count++;
            }
        }
        arr[i] = count;
    }

    for (int i = 0; i < posList.size(); i++) {
        max = Math.max(max, arr[i]);
    }

    for (int i = 0; i < posList.size(); i++) {
        if (max == arr[i]) {
            max = i;
            break;
        }
    }

    if (completed == n*n-1) {
        for (int i = 0 ; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 0) {
                    return new Pos(i, j);
                }
            }
        }
    }

    return posList.get(max);

}

 

---

 

🦈 가중치 계산하기

• 각 좌석별로, 자기 주변 4방향에 대해 그 좌석에 앉은 애가 좋아하는 애가 몇 명 앉아있는지를 계산
• 주변에 0명이라면 그대로 0
• 1명 이상이라면 10 ^ around - 1 이 점수이다.

private static int findAround(int index) {
    Pos pos = isSit[index];
    ArrayList<Integer> like = likes[index];
    int count = 0;
    for (int i = 0; i < 4; i++) {
        int nextX = pos.x + dirX[i];
        int nextY = pos.y + dirY[i];

        if (!isValid(nextX, nextY)) {
            continue;
        }

        for (Integer likeIndex : like) {
            if (isSit[likeIndex].x == nextX && isSit[likeIndex].y == nextY) {
                count++;
            }
        }

    }

    return count;
}

 

 

---

 

 

 

 

🦈 전체코드 

import java.io.*;
import java.util.*;
public class p21608 {
    static int n, completed;
    static Pos[] isSit;
    static int[][] map;
    static int[][] temp;
    static ArrayList<Integer>[] likes;
    static int[] dirX = { -1, 1, 0, 0 };
    static int[] dirY = { 0 , 0 ,-1, 1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        isSit = new Pos[n*n+1];
        map = new int[n][n];
        likes = new ArrayList[n*n+1];

        int[] order = new int[n*n];
        int answer = 0;
        completed = 0;

        for (int i = 0; i < n*n+1; i++) {
            likes[i] = new ArrayList<>();
        }

        for (int i = 0; i < n*n; i++) {
            st = new StringTokenizer(br.readLine());
            int index = Integer.parseInt(st.nextToken());
            order[i] = index;
            for (int j = 0; j < 4; j++) {
                likes[index].add(Integer.parseInt(st.nextToken()));
            }
        }

        for (int i = 0; i < n*n; i++) {
            int index = order[i];
            Pos seat = findSeat(index);
            isSit[index] = seat;
            map[seat.x][seat.y] = index;
            completed++;
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int around = findAround(map[i][j]);
                if (around != 0) {
                    answer += Math.pow(10, (double) around - 1);
                }
            }
        }

        System.out.println(answer);
    }

    private static int findAround(int index) {
        Pos pos = isSit[index];
        ArrayList<Integer> like = likes[index];
        int count = 0;
        for (int i = 0; i < 4; i++) {
            int nextX = pos.x + dirX[i];
            int nextY = pos.y + dirY[i];

            if (!isValid(nextX, nextY)) {
                continue;
            }

            for (Integer likeIndex : like) {
                if (isSit[likeIndex].x == nextX && isSit[likeIndex].y == nextY) {
                    count++;
                }
            }

        }

        return count;
    }

    private static Pos findSeat(int index) {
        temp = new int[n][n];
        for (int s: likes[index]) {
            if (isSit[s] != null) {
                for (int i = 0; i < 4; i++) {
                    int nextX = isSit[s].x + dirX[i];
                    int nextY = isSit[s].y + dirY[i];

                    if (!isValid(nextX, nextY)) {
                        continue;
                    }

                    if (map[nextX][nextY] != 0) {
                        continue;
                        // 이미 누가 앉아있다면 거긴 못앉으니까
                    }
                    temp[nextX][nextY]++;
                }
            }
        }

        ArrayList<Pos> posList = maxCount(findMax());
        Pos answer;
        if (posList.size() == 1) {
            answer = posList.get(0);
        }
        else {
            answer = findEmptyMax(posList);
        }
        return answer;
    }

    private static Pos findEmptyMax(ArrayList<Pos> posList) {
        int[] arr = new int[posList.size()];
        int max = -11;
        for (int i = 0; i < posList.size(); i++) {
            int count = 0;
            if (map[posList.get(i).x][posList.get(i).y] != 0) {
                arr[i]= -1;
                continue;
            }
            for (int j = 0; j < 4; j++) {
                int nextX = posList.get(i).x + dirX[j];
                int nextY = posList.get(i).y + dirY[j];

                if (!isValid(nextX, nextY)) {
                    continue;
                }

                if (map[nextX][nextY] == 0) {
                    count++;
                }
            }
            arr[i] = count;
        }

        for (int i = 0; i < posList.size(); i++) {
            max = Math.max(max, arr[i]);
        }

        for (int i = 0; i < posList.size(); i++) {
            if (max == arr[i]) {
                max = i;
                break;
            }
        }

        if (completed == n*n-1) {
            for (int i = 0 ; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] == 0) {
                        return new Pos(i, j);
                    }
                }
            }
        }

        return posList.get(max);

    }

    private static int findMax() {
        int max = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, temp[i][j]);
            }
        }
        return max;
    }

    private static ArrayList<Pos> maxCount(int max) {
        ArrayList<Pos> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (temp[i][j] == max) {
                    list.add(new Pos(i, j));
                }
            }
        }
        return list;
    }
    private static boolean isValid(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= n) {
            return false;
        }
        return true;
    }
    static class Pos {
        int x;
        int y;
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}