[JAVA] 백준 21608 상어 초등학교

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

21608번: 상어 초등학교

 

1. 서론

 

손에 꼽히는 스스로 풀어낸 골드 문제(감격). 골5라서 그런가 ㅎ

나는 처음에 그냥 list로 풀었는데 PriorityQueue, 즉 우선순위 큐를 이용해면 조금 더 간결하게 풀 수 있다! (우선순위 때문에 계속 정렬해야 해서)

 

2. 문제 풀이

 

숫자 n이 주어진다. 학생들의 숫자는 n^2이다. n^2명의 학생들을 자리 배치할 예정인데 여기에는 제약조건이 있고, 그 제약조건에는 우선순위가 있다. (그래서 우선순위 큐를 써야 하는구나... 방금 깨달음) 그 조건과 우선순위는 다음과 같다.

 

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

 

*학생별로 좋아하는 학생 4명 입력받음

 

이 우선순위를 구현하기 위해서는 우선순위에 따른 정렬을 해야 했다.

 

1순위: 인접한 칸에 좋아하는 학생이 가장 많은 자리

2순위: 인접한 칸에 비어있는 칸이 가장 많은 자리

3순위: 행의 번호가 가장 작은 자리

4순위: 열의 번호가 가장 작은 자리

 

우선순위가 4개나 되다 보니까 if, else문 위치를 헷갈려서 좀 헤맸다.

여하튼 이 우선순위는 자바의 Comparable 클래스의 CompareTo로 구현했다.

한 좌석당 좌표, 인근 좋아하는 학생 수, 인근 빈자리의 값을 전부 가지고 있어야 우선순위를 구현할 수 있기 때문에 클래스를 하나 만들어서 사용했다.

 

좌석을 2차원 배열로 구현하고 n^2명의 학생을 각자 자리 배치해줄 때마다 아래의 과정을 반복한다.

 

1. 빈칸을 탐색

2. 빈칸인 경우 |r1 - r2| + |c1 - c2| = 1의 조건에 맞춘 거리에 있는, 즉 현재 위치에서 동, 서, 남, 북의 자리를 탐색, 좋아하는 학생 수 cnt, 빈자리 수 cnt

3. 우선순위 큐에 저장, 자동으로 우선순위별로 정렬

4. 우선순위 큐의 맨 앞 값을 poll해서 좌석 배치

 

이렇게 우선순위에 맞춘 좌석배치 후 각 학생별로 인근의 좋아하는 학생 수에 따라서 점수를 매기고 출력한다.

 

신경 써줘야 하는 부분이 한 둘이 아니다 보니 5중 for문을 돌려야 했을 때는 이 문제를 포기하고 싶었다...(방법이 틀린 줄 알고)

 

3. 코드 설명

 

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

public class Main {
	
	static int[][] map, like;
	static int n;
	static PriorityQueue<Student> list;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        like = new int[n * n][5]; //좋아하는 학생
        for (int i = 0; i < n * n; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	int x = 0;
        	while (st.hasMoreTokens())
        		like[i][x++] = Integer.parseInt(st.nextToken());
        }
        
        map = new int[n][n]; //자리
        for (int i = 0; i < n * n; i++)
        	select(i);
        
        score();
    }
    
    public static void score() { //점수 계산
    	int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};
    	
    	int sum = 0;
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			int cnt = 0;
    			
				for (int k = 0; k < 4; k++) {//인접거리 체크
					int nx = i + dx[k], ny = j + dy[k];
					
					if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
						for (int x = 0; x < n * n; x++) {
							if (map[i][j] == like[x][0]) {
								for (int q = 1; q <= 4; q++)
									if (map[nx][ny] == like[x][q])//좋아하는 학생 수 cnt
										cnt++;
								break;
							}
						}
					}
				}
				
				switch(cnt) { //점수 계산
					case 1: 
						sum++;
						break;
					case 2:
						sum += 10;
						break;
					case 3:
						sum += 100;
						break;
					case 4:
						sum += 1000;
						break;
				}
    		}
    	}
    	
    	System.out.println(sum);
    }
    
    public static void select(int idx) { //좌석 선택
    	int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};
    	list = new PriorityQueue<>(); //비어있는 칸의 좌표, 주변의 친구, 빈자리 저장
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			if (map[i][j] == 0) {
    				int cnt = 0, empty = 0;
    				
    				for (int k = 0; k < 4; k++) { //인접 거리 체크
    					int nx = i + dx[k], ny = j + dy[k];
    					if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
    						for (int q = 1; q <= 4; q++) { //좋아하는 학생 cnt
    							if (map[nx][ny] == like[idx][q])
    								cnt++;
    						}
    						if (map[nx][ny] == 0) //빈자리 cnt
								empty++;
    					}
    				}
    				list.add(new Student(i, j, cnt, empty));
    			}
    		}
    	}
    	
    	Student s = list.poll();
    	map[s.x][s.y] = like[idx][0]; //자리정함
    } 
}
class Student implements Comparable<Student> {// 좌표, 좋아하는 학생 수, 빈자리 수
	int x, y, cnt, empty;
	
	public Student(int x, int y, int cnt, int empty) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
		this.empty = empty;
	}

	@Override
	public int compareTo(Student o) {// 우선순위 구현
		if (o.cnt == cnt) {
			if (o.empty == empty) {
				if (o.x == x)
					return y - o.y;
				return x - o.x;
			}
			return o.empty - empty;
		}
		return o.cnt - cnt;
	}
}

 

문제가 좀 복잡해서 코드가 엄청 길다 ㅠㅠ

Student클래스를 구현해서 좌표, 좋아하는 학생수, 빈칸을 저장해준다.

compareTo에서 정렬하는 법!!

return 할 때 o.cnt가 앞에 오면 내림차순 cnt가 앞에 오면 오름차순이다.

우선순위 큐는 큐에 값을 넣을 때마다 정렬을 알아서 해주기 때문에 따로 sort를 돌릴 필요가 없다.

 

select 함수에서 자리를 선택하고 score함수에서 점수를 내준다.

like배열에 첫 번째 값은 학생의 번호이고 나머지 4개는 그 학생이 좋아하는 학생들이다.

그런데 2차원 배열 + 동서남북 + 좋아하는 학생 4명을 동시에 체크해야 하기 때문에 5중 for문을 써야 했다... ㅠㅠ

(저걸 안 헷갈리고 생각한 내가 기특^^)