BAEK_17822_원판돌리기

11월 13일 in Category / Algorithm

BAEKJOON

17822. 원판돌리기

…왜 못풀었을까……..?????…….??..?…??? 1솔할 수 있었는데 반성합시다…

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, T, disk[][];
	static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static boolean visited[][];
	static Queue<Integer> q;

	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(in.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());

		disk = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				disk[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0, x = 0, d = 0, k = 0; i < T; i++) {
			st = new StringTokenizer(in.readLine());
			x = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			rotate(x, d, k);
			if(!remove()) {
				average();
			}
		}

		System.out.println(getSum());
	}

	private static int getSum() {
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				sum += disk[i][j];
			}
		}
		return sum;
	}

	private static void rotate(int x, int d, int k) {
		// d = 0 시계방향 증가
		// d = 1 반시계방향 감소
		if (d == 0)
			d = 1;
		else
			d = -1;

		for (int disk_i = x - 1; disk_i < N; disk_i += x) {
			disk[disk_i] = rotate_line(disk_i, d, k);
		}
	}

	private static int[] rotate_line(int index, int d, int k) {
		int array[] = new int[M];

		for (int i = 0; i < M; i++) {
			array[circleM(i + (d * k))] = disk[index][i];
		}

		return array;
	}

	private static boolean remove() {
		boolean flag = false;
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j] && disk[i][j] != 0) {
					visited[i][j] = true;
					flag = flag | bfs(i, j);
				}
			}
		}
		return flag;
	}

	private static boolean bfs(int i, int j) {
		boolean flag = false;
		q = new LinkedList<Integer>();

		q.offer(i);
		q.offer(j);

		int r, c, dr, dc, key = disk[i][j];

		while (!q.isEmpty()) {
			for (int k = 0, size = q.size() / 2; k < size; k++) {
				r = q.poll();
				c = q.poll();
				for (int d = 0; d < 4; d++) {
					dr = r + dir[d][0];
					dc = circleM(c + dir[d][1]);
					if (check(dr) && !visited[dr][dc] && disk[dr][dc] == key) {
						visited[dr][dc] = true;
						q.offer(dr);
						q.offer(dc);
						flag = true;
						disk[dr][dc] = 0;
					}
				}
			}
		}
		if (!flag) {
			visited[i][j] = false;
		} else {
			disk[i][j] = 0;
		}
		return flag;
	}

	private static boolean check(int r) {
		if (r < 0 || r >= N)
			return false;
		return true;
	}

	private static void average() {
		int sum = 0, cnt = 0;
		double avg = 0.0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (disk[i][j] != 0) {
					sum += disk[i][j];
					cnt++;
				}
			}
		}
		avg = sum / (double) cnt;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (disk[i][j] == 0 || disk[i][j] == avg)
					continue;
				if (avg < disk[i][j]) {
					disk[i][j]--;
				} else {
					disk[i][j]++;
				}
			}
		}

	}


	private static int circleM(int index) {
		if (index < 0)
			return index + M;
		if (M <= index)
			return index - M;
		else
			return index;
	}
}