백준 [17822] 원판돌리기
문제보기
풀이
소스코드
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++;
}
}
}
}
}