백준 17140 : 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

[ 문제풀이 ]

주어진 조건에 따라 시뮬레이션을 돌리는 문제이다. 100개를 초과하는 숫자는 제외하기 때문에 이 부분만 조심해서 구현한다면 쉽게 해결할 수 있을 것이다.

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

public class Main {

	static int r, c, k;
	static int rowLen, colLen;
	static int[][] map;
	static Node[] node;
	static List<Node> nodes;

	static class Node implements Comparable<Node> {
		int number, cnt;

		public Node(int number, int cnt) {
			this.number = number;
			this.cnt = cnt;
		}

		public int compareTo(Node o) {
			if (this.cnt == o.cnt) return this.number - o.number;
			return this.cnt - o.cnt;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		map = new int[101][101];
		for (int i = 1; i <= 3; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= 3; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		rowLen = 3;
		colLen = 3;
		node = new Node[101];
		nodes = new ArrayList<>();

		int time = 0;
		do {
			if (map[r][c] == k) break;
			
			if (rowLen >= colLen) sortRow();
			else sortCol();
		} while (time++ < 100);

		bw.write((time == 101 ? -1 : time) + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void init() {
		nodes.clear();
		for (int i = 1; i <= 100; ++i) node[i] = null;
	}

	public static void sortRow() {
		int maxCol = 0;

		//모든 행을 돌면서
		for (int i = 1; i <= Math.min(100, rowLen); ++i) {
			for (int j = 1; j <= Math.min(100, colLen); ++j) {
				int num = map[i][j];

				//숫자와 숫자가 나온 횟수 갱신
				if (node[num] == null) node[num] = new Node(num, 1);
				else node[num].cnt++;
			}

            //나온 숫자들을 리스트에 넣어줌
			for (int j = 1; j <= 100; ++j) {
				if (node[j] != null) {
					nodes.add(node[j]);
				}
			}

			Collections.sort(nodes);
			
			maxCol = Math.max(maxCol, nodes.size() * 2);

			//리스트에 있는 숫자, 횟수를 차례대로 map에 갱신
			//100개 까지 남은 map은 0으로 갱신
			for (int j = 1, k = 0; j <= 100; j += 2, ++k) {
				if (k < Math.min(nodes.size(), 50)) {
					Node node = nodes.get(k);
					map[i][j] = node.number;
					map[i][j + 1] = node.cnt;
				} else {
					map[i][j] = 0;
					map[i][j + 1] = 0;
				}
			}
			init();
		}
		//최대 열의 개수 갱신
		colLen = maxCol;
	}

	public static void sortCol() {
		int maxRow = 0;
		
		//모든 열을 돌면서
		for (int j = 1; j <= Math.min(100, colLen); ++j) {
			for (int i = 1; i <= Math.min(100, rowLen); ++i) {
				int num = map[i][j];
				
				//숫자와 숫자가 나온 횟수 갱신
				if (node[num] == null) node[num] = new Node(num, 1);
				else node[num].cnt++;
			}

			//나온 숫자들을 리스트에 넣어줌
			for (int i = 1; i <= 100; ++i) {
				if (node[i] != null) {
					nodes.add(node[i]);
				}
			}

			Collections.sort(nodes);
			
			maxRow = Math.max(maxRow, nodes.size() * 2);

			//리스트에 있는 숫자, 횟수를 차례대로 map에 갱신
			//100개 까지 남은 map은 0으로 갱신
			for (int i = 1, k = 0; i <= 100; i += 2, ++k) {
				if (k < Math.min(nodes.size(), 50)) {
					Node node = nodes.get(k);
					map[i][j] = node.number;
					map[i + 1][j] = node.cnt;
				} else {
					map[i][j] = 0;
					map[i + 1][j] = 0;
				}
			}
			init();
		}
		//최대 행의 개수 갱신
		rowLen = maxRow;
	}
}