[BOJ 21608] 상어 초등학교

문제

• BOJ 21608
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

실버1이라서 쉬울 줄 알았는데 런타임에러가 나와서 보니까 처음에는 likeCnt!=0 || zeroCnt!=0인 좌표들만 pq에 넣어줬는데 그렇게 되면 마지막 번호이고 주변에 likeCnt가 없는 경우는 pq에 값이 안들어가므로 poll()했을 때 에러가 발생한다.
그래서 모든 경우에 대해 pq에 넣어주니 해결되는 문제였다.

1. findSeat(int num에서 학생 순서대로 자리를 찾는다.
   • 좌표 1,1부터 N,N까지 돌면서 4방향 탐색을 하면서 인접한 칸에 존재하는 좋아하는 수, 빈칸 수를 기록하고 pq에 넣는다.
   • 모든 조사가 끝나면 pq에서 하나 꺼내서 자리를 확정짓는다.
   • pq의 타입은 Point클래스인데 여기서 Comparable로 1)좋아하는 학생이 많은 순, 2)빈칸이 많은 순, 3)행과 열이 작은 순으로 정렬해주므로 이를 모두 만족하는 자리가 꺼내진다.
2. 모든 학생의 자리를 찾았으면 map을 돌면서 getSatisfy(int i, int j)에서 주변에 인접한 좋아하는 학생 수를 카운트해서 그에 따른 만족도를 Ans에 누적합한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[] satisfy = { 0, 1, 10, 100, 1000 }; // 만족도
	static int N;
	static int[][] map; // 확정된 학생 자리
	static PriorityQueue<Point> pq;
	static int[][][] students; // i:현재번호, j:전체 번호, k:좋아하면 1,아니면 0
	static int[] order; // 자리 정하는 순서
	static int sCnt; // 학생 수
	static int[][] dArr = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int Ans; // 만족도 합

	static class Point implements Comparable<Point> {
		int x, y;
		int likeCnt; // 인접해있는 좋아하는 사람 수
		int zeroCnt; // 인접해있는 빈칸 수

		public Point(int x, int y, int likeCnt, int zeroCnt) {
			this.x = x;
			this.y = y;
			this.likeCnt = likeCnt;
			this.zeroCnt = zeroCnt;
		}

		@Override
		public int compareTo(Point o) {
			if (this.likeCnt == o.likeCnt) { // 1. 좋아하는 학생이 많은 순
				if (this.zeroCnt == o.zeroCnt) { // 2. 빈칸이 많은 순
					if (this.x == o.x)
						return Integer.compare(this.y, o.y); // 3. 행,열 작은순
					else
						return Integer.compare(this.x, o.x);
				} else
					return Integer.compare(o.zeroCnt, this.zeroCnt);
			} else
				return Integer.compare(o.likeCnt, this.likeCnt);
		}
	}

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		map = new int[N + 1][N + 1];
		sCnt = (int) Math.pow(N, 2);
		students = new int[sCnt + 1][(int) (sCnt + 1)][1];
		order = new int[sCnt + 1];

		for (int i = 1; i <= sCnt; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken()); // 번호
			for (int j = 0; j < 4; j++) {// 좋아하는 학생 번호
				int likeNum = Integer.parseInt(st.nextToken());
				students[num][likeNum][0] = 1;
				order[i] = num;
			}
		} // End input

		for (int k = 1; k <= sCnt; k++) { // 각 학생의 자리 구하기
			int num = order[k];
			findSeat(num);
		}

		// 자리 확정 후 만족도의 총 합 구하기
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				Ans += satisfy[getSatisfy(i, j)];
			}
		}
		System.out.println(Ans);
	}

	private static int getSatisfy(int i, int j) {
		int likeCnt = 0;

		for (int d = 0; d < 4; d++) {
			int nx = i + dArr[d][0];
			int ny = j + dArr[d][1];

			if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
				if (students[map[i][j]][map[nx][ny]][0] == 1)
					likeCnt++;
			}
		}

		return likeCnt;
	}
	
	private static void findSeat(int num) {
		pq = new PriorityQueue<>();

		for (int i = 1; i <= N; i++) { // 모든 칸 조사
			for (int j = 1; j <= N; j++) {
				if (map[i][j] != 0) continue;

				// 인접한 칸에 좋아하는 학생이 있는지 확인
				int likeCnt = 0;
				int zeroCnt = 0;

				for (int d = 0; d < 4; d++) {
					int nx = i + dArr[d][0];
					int ny = j + dArr[d][1];

					if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
						// 좋아하는 학생있는지
						if (students[num][map[nx][ny]][0] == 1)
							likeCnt++;
						else if (map[nx][ny] == 0)
							zeroCnt++;
					}
				} // 인접칸 조사 끝
				pq.add(new Point(i, j, likeCnt, zeroCnt)); // 후보로 넣음
			}
		}

		// 확정 자리 하나 꺼내기
		Point p = pq.poll();
		map[p.x][p.y] = num;
	}
}