백준 21608 상어 초등학교

문제

백준 21608번 상어 초등학교 링크

오늘은 문제가 길어서 입출력만 올렸다.

풀이 방법

문제를 보면 입력값의 범위가 최대 20이므로 굉장히 작은 것을 알 수 있다. 따라서 매번 완전탐색을 해도 제한시간을 넘지 않는다는 것을 생각했다.

1. 좋아하는 사람들을 리스트 배열로 저장

먼저 문제를 보자마자 든 생각은 방향이 있는 그래프라고 생각했다. 따라서 인접리스트 배열처럼 각 사람의 인덱스에 있는 리스트에 그 사람이 좋아하는 사람들을 추가하였다.

2. 자리를 바꿀 순서의 사람마다 교실을 한칸식 검사 후 우선순위 큐에 사용하기

자리를 순서의 사람마다 2차원 배열 교실을 검사한다. 1칸씩 잡고, 그 자리가 비어있으면 그 자리로부터 4방향 탐색을 통해 인접한 사람의 개수와 인접한 비어있는 자리의 개수를 구한다. 이후 이 값들을 클래스로 만들어 우선순위 큐에 저장한다.

3. 우선순위 큐에서 우선순위 적용 후 우선순위 큐 비우기

각 사람마다 자리를 정해주기 위해서 우선순위 큐에서 우선순위가 가장 높은 자리를 하나 뽑는다. 이때 문제에서 제시한 우선순위가 적용되도록 우선순위큐를 좋아하는 인접 개수 > 비어있는 인접 개수 > 행 > 열 우선순위로 비교하도록 한다.
또한 한 사람은 한자리밖에 못앉으므로 자리를 뽑고난 뒤 큐를 초기화한다(비운다).

4. 자리배치가 끝난 후 점수 다시 계산하기

자리배치가 끝난 뒤 2차원 배열인 교실을 돌면서 4방향 탐색을 통해 점수를 계산한다.

자리배치 시에 계산한 인접점수를 사용하면 되지 않겠냐고 생각할 수 있지만 내가 좋아하는 사람이 나보다 자리 정하는 순서가 낮으면서 나의 자리와 인접하게 앉을 수 있으므로 점수는 바뀔 수 있다.
따라서 자리배치 후 다시 점수를 계산해주어야한다.

정답 코드

import java.io.*;
import java.util.*;

public class p21608 {
    static int total;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        total = Integer.parseInt(st.nextToken()); // 가로 및 세로 줄
        int totalPerson = total * total; //전체 학생 수
        List<Integer> [] likes = new List[totalPerson+1]; // 좋아하는 학생 인접 리스트
        int [] seq = new int[totalPerson]; // 자리 지정 순서 배열
        int [][] classroom = new int[total][total]; // 교실 현재 자리 2차원 배열
        int result = 0; // 정답

        int [] dx = {-1, 0, 0, 1};
        int [] dy = {-0, -1, 1, 0};
        // A형 PQ  우선순위: adj > vacant > row > col
        PriorityQueue<A> pq = new PriorityQueue<>((o1, o2) -> {
            if(o1.adjNum != o2.adjNum) return o2.adjNum - o1.adjNum;
            if(o1.vacantNum != o2.vacantNum) return o2.vacantNum - o1.vacantNum;
            if(o1.row != o2.row) return o2.row - o1.row;
            return o2.col - o1.col;
        });

        // 좋아하는 학생 인접 리스트 초기화
        for(int i=0; i<=totalPerson; i++){
            likes[i] = new ArrayList<>();
        }
        // 좋아하는 학생 인접 리스트 입력 받기
        for(int t = 0; t<totalPerson; t++){
            st = new StringTokenizer(br.readLine());
            int now = Integer.parseInt(st.nextToken());
            seq[t] = now;
            for(int a = 0; a<4; a++){
                likes[now].add(Integer.parseInt(st.nextToken()));
            }
        }
        for(int s = 0; s<totalPerson; s++){ //모든 seq에 있는 사람들에 대해
            int p = seq[s]; //현재 자리를 정하는 사람
            //1. 교실에서 한칸씩 검사
            for(int i =0; i<total; i++){
                for(int j=0; j<total; j++){
                    int nowX = j;
                    int nowY = i;
                    if(classroom[nowY][nowX]!=0) continue;
                    List<Integer> likeFour = likes[p];
                    int vac = 0; // 비어있는 인접한 개수
                    int adj = 0; // 좋아하는 인접한 개수
                    for(int k=0; k<4; k++){
                        int newX = j+dx[k];
                        int newY = i+dy[k];
                        if(check(newX, newY)){ //범위 안에 있으면
                            if(classroom[newY][newX] == 0) vac++; // 비어있으면
                            else if(likeFour.contains(classroom[newY][newX])) adj++; //좋아하는 인접한 사람이면
                        }
                    }
                    // 4방 탐색후 PQ에 넣기
                    pq.add(new A(adj, vac, nowY, nowX));
                }
            }
            A poll = pq.poll(); //앉을 사람
            classroom[poll.row][poll.col] = p; //착석
            pq.clear();
        }

        //정답 구하기
        for(int i=0; i<total; i++){
            for(int j=0; j<total; j++){
                int nowPerson = classroom[i][j];
                int cnt = 0; // 좋아하는 인접한 개수
                List<Integer> likeFour = likes[nowPerson];
                for(int k=0; k<4; k++){
                    int newX = j+dx[k];
                    int newY = i+dy[k];
                    if(check(newX, newY)){ //범위 안에 있으면
                        if(likeFour.contains(classroom[newY][newX])) cnt++; //좋아하는 인접한 사람이면
                    }
                }
            result += calResult(cnt);
            }
        }
        bw.write(result+"");
        bw.flush();
        bw.flush();
    }
    // 범위 내에 있는지 체크
    static boolean check(int x, int y){
        return x>=0 && x<total && y>=0 && y<total;
    }
    static int calResult(int num){
        switch (num){
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return 10;
            case 3:
                return 100;
            default:
                return 1000;
        }
    }

}
class A{
    int adjNum; // 좋아하는 사람 인접 개수
    int vacantNum; // 비어있는 자리 인접 개수
    int row; // 행
    int col;// 열

    public A(int adjNum, int vacantNum, int row, int col) {
        this.adjNum = adjNum;
        this.vacantNum = vacantNum;
        this.row = row;
        this.col = col;
    }
}