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

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

21608번: 상어 초등학교

 

 

 

문제

N*N크기의 교실에 N^2명의 학생들이 자리를 정하려고 한다.

 

자리를 정하는 학생의 순서와, 그 학생들이 좋아하는 학생의 번호가 주어진다.

한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.

 

주어진 조건은 이렇다

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

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

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

위의 예시를 주어지는 조건대로 자리를 정해준다면

이렇게 결과가 나온다. 

자리 배치가 모두 끝난 후에 학생의 만족도를 구한다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

 

 

 

풀이

학생 수 의 범위가 3<=N<=20이어서 최대 400명이라 학생 한 명이 들어올 때마다 교실의 자리를 전부 탐색하는 방법을 구현하였다.

 

1.  교실에서 빈자리를 체크하며 주어지는 조건 1,2,3 순서에 맞게 PQ에 넣어 정렬시킨다. (=교실의 빈자리를 PQ에 넣었을 때 문제에서 주어지는 조건의 순서대로 정렬되게끔 조건을 준다.)

2. 교실의 전체 탐색을 마친 후 PQ에서 가장 앞에 오는 자리가 빈자리가 맞는지 확인하고, 맞다면 학생의 자리를 고정시킨다.

2-1. 학생들의 만족도 조사에서 다시 사용하기 위해 이차원 ArrayList배열을 만들어서 고정된 학생이 좋아하는 학생의 번호 4개의 ArrayList를 저장해둔다.

3. 1~2 과정을 다 반복해서 모든 자리에 학생들이 앉았다면, 2-1에서 만들었던 이차원 ArrayList 배열을 이용하여 학생들의 만족도를 계산하여 출력한다. (10의 제곱으로 표현이 가능해서 Math.pow 사용)

 

 

 

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static int[] di = {-1,1,0,0};
	static int[] dj = {0,0,-1,1};
	static int N;
	static int[][] classroom;
	static ArrayList<Integer>[][] best;
	static PriorityQueue<Point> pq;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		classroom = new int[N][N];
		pq = new PriorityQueue<>();
		best = new ArrayList[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				best[i][j] = new ArrayList<>();
			}
		}
		
		for(int i=0; i<N*N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			
			int student = Integer.parseInt(st.nextToken());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			Seat(student, a, b, c, d);
		}
		
		int tot = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				int like = 0;
				for(int d=0; d<4; d++) {
					int ni = i + di[d];
					int nj = j + dj[d];
					if(ni>=0 && ni<N && nj>=0 && nj<N) {
						if(best[i][j].contains(classroom[ni][nj])) like++;
					}
				}
				if(like>0) tot += (int)Math.pow(10, (like-1));
			}
		}
		System.out.println(tot);
		
	}
	private static void Seat(int student, int n1, int n2, int n3, int n4) {
		
		ArrayList<Integer> list = new ArrayList<>();
		list.add(n1);
		list.add(n2);
		list.add(n3);
		list.add(n4);
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				
				if(classroom[i][j]==0) {
					//1. 비어 있는 상태에서 인접한 칸에 좋아하는 친구가 얼마나 있는지 센다
					//2. 인접한 칸 중에서 빈 칸이 얼마인지 센다
					int empty = 0;
					int favor = 0;
					for(int d=0; d<4; d++) {
						int ni = i + di[d];
						int nj = j + dj[d];
						if(ni>=0 && ni<N && nj>=0 && nj<N) {
							if(classroom[ni][nj]==0) empty++;
							else if(list.contains(classroom[ni][nj])) favor++;
						}
					}
					pq.offer(new Point(i, j, empty, favor));
					
				}
			}
		}
		while(!pq.isEmpty()) {
			
			Point cur = pq.poll();
			
			if(classroom[cur.i][cur.j]>0) continue;
			else {
				classroom[cur.i][cur.j] = student;
				best[cur.i][cur.j] = list;
				break;
			}
		}
		pq.clear();
	}
	
	static class Point implements Comparable<Point>{
		int i;
		int j;
		int cnt; //비어있는 칸의 개수 저장
		int friend;
		public Point(int i, int j, int cnt, int friend) {
			this.i = i;
			this.j = j;
			this.cnt = cnt;
			this.friend = friend;
		}
		@Override
		public int compareTo(Point o) {
			if(this.friend == o.friend) {
				if(this.cnt == o.cnt) return this.j-o.j;
				else return o.cnt - this.cnt;
			}
			return o.friend-this.friend;
		}
	}
}