[삼성기출]백준17779 - 게리맨더링2

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

public class Main {
	static int r, c, k;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().trim().split(" ");
		r = Integer.parseInt(input[0]) - 1;			// 인덱스 0부터 시작하기 때문에 -1처리
		c = Integer.parseInt(input[1]) - 1;
		k = Integer.parseInt(input[2]);
		map = new int[3][3];
		for (int i = 0; i < 3; i++) {
			input = br.readLine().trim().split(" ");
			for (int j = 0; j < 3; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		for (int t = 0; t <= 100; t++) {
			R = map.length;
			C = map[0].length;
			
			if (r<R && c<C && map[r][c] == k) { // 해당 r,c 위치에 k 값 있는지 체크.
				System.out.println(t);			// 있으면 프린트하고 return.
				return;
			}
			play();			// 연산
//			print();
		}
		System.out.println(-1);
	}
	static Queue<Number> addNumber(int[] numbers) {		// 디버깅하기 편하게 함수화
		Queue<Number> qu = new PriorityQueue<>();
		for (int j = 1; j < 101; j++) {
			if (numbers[j] != 0) qu.add(new Number(j, numbers[j]));
		}
		return qu;
	}
	static int R, C;
	static void initArr() {
		for (int i = 0; i < 20001; i++) {
			if (arr[i] != 0)
			arr[i] = 0;
			else return;
		}
	}
	static int[] arr = new int[20001];
	static void play() {
		initArr();
		Queue<Number> qu;
		int[] numbers;
		Number number;
		int size, seq;
		if(R >= C) {
			size = 3;
			seq = 0;
			for (int i = 0; i < R; i++) {
				numbers = new int[101];
				for (int j = 0; j < C; j++) {
					numbers[map[i][j]]++;
				}
				qu = addNumber(numbers);
				if (size < qu.size() * 2)
				size = qu.size() * 2;
				while (!qu.isEmpty()) {
					number = qu.poll();
					arr[seq++] = number.num;
					arr[seq++] = number.cnt;
				}
				arr[seq++] = -1;
			}
			seq = 0;
			C = size;
			map = new int[R][C];
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C + 1; j++) {
					if (arr[seq] == -1) {
						seq++;
						break;
					}
					else if (j < C)
					map[i][j] = arr[seq++];
				}
			}
		}else {
			seq = 0;
			size = 3;
			for (int j = 0; j < C; j++) {
				numbers = new int[101];
				for (int i = 0; i < R; i++) {
					numbers[map[i][j]]++;
				}
				qu = addNumber(numbers);
				if (size < qu.size() * 2)
				size = qu.size() * 2;
				while (!qu.isEmpty()) {
					number = qu.poll();
					arr[seq++] = number.num;
					arr[seq++] = number.cnt;
				}
				arr[seq++] = -1;
			}
			seq = 0;
			R = size;
			map = new int[R][C];
			for (int j = 0; j < C; j++) {
				for (int i = 0; i < R + 1; i++) {
					if (arr[seq] == -1) {
						seq++;
						break;
					}
					else if (i < R)
					map[i][j] = arr[seq++];
				}
			}
		}
	}
	static class Number implements Comparable<Number> {
		int num, cnt;
		public Number(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		@Override
		public String toString() {
			return "[" + num + "," + cnt + "]";
		}
		/*
         * 
         * cnt 오름차순, num 오름차
         * 
         */
		@Override
		public int compareTo(Number o) {
			if (this.cnt < o.cnt)
			return -1;
			else if (this.cnt == o.cnt) {
				if (this.num < o.num)
				return -1;
				else return 1;
			}
			else return 1;
		}
	}
	static void print() {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("========================");
	}
}