문제 이해

교실은 N X N 크기의 격자로 나타낼 수 있다.
학교에 다니는 학생 수는 $N^2$일 때, 학생의 자리를 정해주려고 한다.

"두 칸이 인접하다"의 의미는 $(r_1, c_1), (r_2, c_2)$가 존재할 때 $|r_1-r_2| + |c_1-c_2| = 1$을 만족하도록 자리가 배치되는 것이다.
(즉, 상하좌우에 배치되는 것)

아래 규칙을 통해 자리를 배치하려 한다.
1. 비어있는 칸 중 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1번을 만족하는 칸이 여러개이면 인접한 칸 중 빈 자리가 가장 많은 칸으로 정한다.
3. 2를 만족하는 칸도 여러개이면 행의 번호가 작은 순, 같은 행이라면 열의 번호가 작은 칸으로 자리를 정한다.

학생과 인접한 칸에 좋아하는 학생 수에 따라 만족도가 정해진다.
1명이면 1, 2명이면 10, 3명이면 100, 4명이면 1000점의 만족도를 가진다.

위 규칙을 통해 학생 자리를 배치했을 경우 학생 만족도의 총 합을 구하는 문제이다.

---

문제 풀이

Brute-Force 이외의 방법이 생각나지 않는 문제였다.

먼저 조건에 맞춰 순서대로 학생들을 배치시킨다.

이렇게 학생들을 배치시킨 이후, 최종 점수를 계산하는 방법으로 풀었다.

배치시키는 도중 점수를 중간 계산하는 방법도 생각은 해봤으나, 사면이 꽉 찰 때 계산이 수행되어야 하는데 이것을 매번 검사하는 것이 더 시간이 오래 걸릴 것 같아 포기했다.

---

코드

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

class Num{
	int blank;
	int love;
	
	public Num(int blank, int love) {
		this.blank = blank;
		this.love = love;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static FastReader sc = new FastReader();
	
	static int N;
	static int[][] arr;
	static ArrayList<Integer>[] lists;
	
	static Num check(int human, int i, int j) {
		
		int blank = 0;
		int love = 0;
        // blank : 상하좌우에서 빈 칸의 개수
        // love : 상하좌우에 존재하는 좋아하는 사람 수
		
		if(i-1>0) {
			if(arr[i-1][j]==0) blank++;
			else if(lists[human].contains(arr[i-1][j])) love++;
		}
		if(j-1>0) {
			if(arr[i][j-1]==0) blank++;
			else if(lists[human].contains(arr[i][j-1])) love++;
		}
		if(i<N) {
			if(arr[i+1][j]==0) blank++;
			else if(lists[human].contains(arr[i+1][j])) love++;
		}
		if(j<N) {
			if(arr[i][j+1]==0) blank++;
			else if(lists[human].contains(arr[i][j+1])) love++;
		}
		
		return new Num(blank, love);
	}
	
	static void setting(int human) {
		int sub_x = 0;
		int sub_y = 0;
		int love = -1;
		int blank = -1;
		
		for(int i =1;i<N+1;i++) {
			for(int j =1;j<N+1;j++) {
				if(arr[i][j]!=0) continue;
				
				Num tmp = check(human, i, j);
				
				if(love < tmp.love) {
                // 좋아하는 사람이 이전 최댓값보다 많다면 위치 갱신
                // 비어 있는 숫자도 아래 연산에 필요하므로 갱신해 줌
					sub_x = i;
					sub_y = j;
					blank = tmp.blank;
					love = tmp.love;
				}
				else if(love==tmp.love && blank < tmp.blank) {
                // 좋아하는 사람 숫자가 같을 경우 2번 규칙에 의해
                // blank(빈 칸) 숫자가 많은 위치를 선택해야 함
                
                // blank=tmp.blank일 경우에는 i, j를 작은 곳에서부터
                // Searchh하므로 고려해주지 않아도 된다.
					sub_x = i;
					sub_y = j;
					blank = tmp.blank;
				}
			}
		}
		arr[sub_x][sub_y] = human;
	}
	
	static int compute() {
    // 상하좌우에 좋아하는 사람 숫자를 세서 만족도 총합을 계산
    // 0일 때는 1/10 = 0.1이므로, (int) 0.1 = 0으로 설정했다
		int ans = 0;
		for(int i =1;i<N+1;i++) {
			for(int j =1;j<N+1;j++) {
				Num tmp = check(arr[i][j], i, j);
				ans += (int) Math.pow(10, tmp.love-1);
			}
		}
		
		return ans;
	}
	
	public static void main(String[] args) {
		N = sc.nextInt();
		
		arr = new int[N+1][N+1];
		
		lists = new ArrayList[N*N+1];
		
		for(int i =1;i<N*N+1;i++) lists[i] = new ArrayList<>();
		
		for(int i =0;i<N*N;i++) {
			int human = sc.nextInt();
			for(int j =0;j<4;j++) {
				lists[human].add(sc.nextInt());
			}
			
			setting(human);
		}
		
		System.out.println(compute());
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과