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

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

21608번: 상어 초등학교

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	static class Seat implements Comparable<Seat> {
		int x, y;
		int like_stu_cnt;
		int empty_seat_cnt;
		
		Seat(int x, int y, int like_stu_cnt, int empty_seat_cnt) {
			this.x=x;
			this.y=y;
			this.like_stu_cnt=like_stu_cnt;
			this.empty_seat_cnt=empty_seat_cnt;
		}
		
		// 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
		// 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
		// 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
	
		@Override
		public int compareTo(Seat o) {
			if(this.like_stu_cnt > o.like_stu_cnt) return -1;
			else if(this.like_stu_cnt == o.like_stu_cnt) {
				if(this.empty_seat_cnt > o.empty_seat_cnt) return -1;
				else if(this.empty_seat_cnt == o.empty_seat_cnt) {
					if(this.x < o.x) return -1;
					else if(this.x == o.x) {
						if(this.y < o.y) return -1;
					}
				}
			}
			return 1;
		}

		@Override
		public String toString() {
			return "Seat [x=" + x + ", y=" + y + ", like_stu_cnt=" + like_stu_cnt + ", empty_seat_cnt=" + empty_seat_cnt
					+ "]";
		}
	}
	
	static int N;
	static int[][] map, dir = {{-1,0}, {1,0}, {0, -1},{0, 1}};
	static int[][] student_info;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		map = new int[N+1][N+1];
		student_info = new int[(N*N)+1][4];
		
		for(int i=0; i<N*N; i++) {
			st = new StringTokenizer(br.readLine());
			int student_num = Integer.parseInt(st.nextToken());
			
			for(int j=0; j<4; j++) {
				student_info[student_num][j] = Integer.parseInt(st.nextToken());
			}
			
			setSeat(student_num);
		}
		
//		print();
		
		// 자리 배치 끝난 후 만족도 구하기
		int answer = 0;
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				
				int n=0;
				
				int stu_num = map[i][j];
				
				for(int k=0; k<4; k++) {
					int nx = i+dir[k][0];
					int ny = j+dir[k][1];
					
					if(isInside(nx, ny)) {
						if(student_info[stu_num][0] == map[nx][ny] ||
								   student_info[stu_num][1] == map[nx][ny] ||
								   student_info[stu_num][2] == map[nx][ny] ||
								   student_info[stu_num][3] == map[nx][ny]) {
									n++;
							}
					}
				}
				
				if(n == 1) answer += 1;
				else if(n == 2) answer += 10;
				else if(n == 3) answer += 100;
				else if(n == 4) answer += 1000;
				
			}
		}
		
		System.out.println(answer);
		
	}
	
	public static void setSeat(int stu_num) {
		
		ArrayList<Seat> list = new ArrayList();
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(map[i][j] != 0) continue;
				
				int empty_count = 0;
				int like_student_cnt = 0;
				
				for(int k=0; k<4; k++) {
					int nx = i+dir[k][0];
					int ny = j+dir[k][1];
					
					if(isInside(nx, ny)) {
						// 1. 좋아하는 학생이 인접한 칸
						if(student_info[stu_num][0] == map[nx][ny] ||
						   student_info[stu_num][1] == map[nx][ny] ||
						   student_info[stu_num][2] == map[nx][ny] ||
						   student_info[stu_num][3] == map[nx][ny]) {
							like_student_cnt++;
						}
						// 2. 비어있는 칸
						else if(map[nx][ny] == 0) {
							empty_count++;
						}
					}
				}
				
				// 3. 행, 열번호
				list.add(new Seat(i, j, like_student_cnt, empty_count));
			}
		}
		
		Collections.sort(list);
		
		Seat seat = list.get(0);
		
		map[seat.x][seat.y] = stu_num;
	}
	
	public static boolean isInside(int x, int y) {
		return x>=1 && y>=1 && x<=N && y<=N;
	}
	
	public static void print() {
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}