원판돌리기


백준 [17822] 원판돌리기

문제보기
Alt text

풀이

  • 시뮬레이션

소스코드

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

public class Main {
	static int N, M, T, ans, cnt;
	static int[][] map;
	static int[][] turn;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		turn = new int[T][3];
		ans = 0;
		cnt = N * M;

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

		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());

			turn[i][0] = x;
			turn[i][1] = d;
			turn[i][2] = k;
		}
		go(0);
	}
    
	public static void go(int t) {
		if (t == T) {
			System.out.println(ans);
			return;
		}

		// K[0] : x, K[1] : d, K[2] : k
		int[] K = { turn[t][0], turn[t][1], turn[t][2] };
		for (int i = 0; i < N; i++) {
			if ((i + 1) % K[0] != 0)
				continue;
			int[] arr = new int[M];
			if (K[1] == 0) { // 시계방향
				for (int j = 0; j < arr.length; j++) {
					arr[(j + K[2]) % M] = map[i][j];
				}
				map[i] = arr;
			} else { // 반시계방향
				for (int j = 0; j < arr.length; j++) {
					arr[j] = map[i][(j + K[2]) % M];
				}
				map[i] = arr;
			}
		}

		boolean flag = remove();
		if (!flag) {
			average();
		}

		go(t + 1);
	}

	public static boolean remove() {
		boolean result = false;
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0)
					continue;

				int num = map[i][j];
				queue.add(new int[] { i, j });
				while (!queue.isEmpty()) {
					int[] q = queue.poll();

					boolean flag1 = false;
					// 좌인접
					int left = q[1] - 1;
					if (left < 0)
						left = M - 1;
					if (num == map[q[0]][left]) {
						map[q[0]][left] = 0;
						cnt--;
						ans -= num;
						flag1 = true;
						queue.add(new int[] { q[0], left });
					}
					// 우인접
					int right = q[1] + 1;
					if (right >= M) {
						right = 0;
					}
					if (num == map[q[0]][right]) {
						map[q[0]][right] = 0;
						cnt--;
						ans -= num;
						flag1 = true;
						queue.add(new int[] { q[0], right });
					}

					boolean flag2 = false;
					// 아래원판인접
					int bottom = q[0] - 1;
					if (bottom >= 0 && num == map[bottom][q[1]]) {
						map[bottom][q[1]] = 0;
						cnt--;
						ans -= num;
						flag2 = true;
						queue.add(new int[] { bottom, q[1] });
					}
					// 위원판인접
					int top = q[0] + 1;
					if (top < N && num == map[top][q[1]]) {
						map[top][q[1]] = 0;
						cnt--;
						ans -= num;
						flag2 = true;
						queue.add(new int[] { top, q[1] });
					}

					if ((flag1 || flag2) && map[q[0]][q[1]] != 0) {
						result = true;
						map[q[0]][q[1]] = 0;
						cnt--;
						ans -= num;
					}
				}
			}
		}
		return result;
	}

	public static void average() {
		float avg = (float) ans / cnt;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0)
					continue;
				if (map[i][j] > avg) {
					map[i][j] -= 1;
					ans--;
				} else if (map[i][j] < avg) {
					map[i][j] += 1;
					ans++;
				}
			}
		}
	}
}