백준 - 원판 돌리기 (17822)

1. 문제

문제 링크

설명

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

2. 풀이

시뮬레이션 문제입니다.
딱히 까다로운 구현 부분도 없으니 도전해봅시다.

계획1 - x의 배수인 원판들을 d 방향으로 k칸 회전시킵니다.

// 1. x의 배수인 원판들을 d 방향으로 k칸 회전시킵니다.
// 방향에 따라 횟수 조정
k = d == 0 ? k : (M - k); 

// x의 부호인 원판을 시계 방향으로 k칸 돌리기
for (int j = x; j <= N; j += x) { 
	for (int l = 1; l <= M; l++) tmp[l] = circle[j][l]; // 해당 원판 복사
	
	for (int l = 1; l <= M; l++) {
		int idx = (l + k) % M;
		idx = idx == 0 ? M : idx;
		
		circle[j][idx] = tmp[l]; // 원판 돌리기
	}
}

반시계 방향으로 1번 회전시킨다는 뜻은
시계 방향으로 3번 회전시킨다는 의미와 동일합니다.
고로 d변수에 따라서 시계 방향으로 몇 칸 회전시킬지 정하고 회전시키면 됩니다.

계획2 - 원판들의 인접한 좌표들에 대해서 지워줍니다.

// 인접한 부분이 0이 아니고 같다면 지우는 함수
static void delete(int y1, int x1, int y2, int x2) {
	if (circle[y1][x1] != 0 
			&&  circle[y2][x2] != 0
			&& circle[y1][x1] == circle[y2][x2]
	) erase[y1][x1] = erase[y2][x2] = isErase = true;
}

isErase = false;

// 인접한 좌표들에 대하여 지워주기
for (int j = 1; j <= N; j++) {
	for (int l = 1; l <= M; l++) {
		delete(j - 1, l, j, l);
		delete(j + 1, l, j, l);
		delete(j, l - 1, j, l);
		delete(j, l + 1, j, l);
	}
	
	delete(j, 1, j, M);
}

문제에 나온 조건대로 지워줬습니다.

계획3 - 인접한 수를 지운 여부에 따라 조건대로 구현합니다.

if (isErase) { // 지워줘야하는 곳이 있다면 지워주기
	for (int j = 1; j <= N; j++) {
		for (int l = 1; l <= M; l++) {
			if (erase[j][l]) {
				circle[j][l] = 0;
			}
			
			erase[j][l] = false;
		}
	}
} else { // 인접한 곳이 없어 지워진 곳이 없을 때
	double avg = 0;
	int cnt = 0;
	
	for (int j = 1; j <= N; j++) {
		for (int l = 1; l <= M; l++) {
			if (circle[j][l] <= 0) continue;
			avg += circle[j][l];
			cnt++;
		}
	}
	
	// 평균 계산
	avg /= 1.0 * cnt;
	
	for (int j = 1; j <= N; j++) {
		for (int l = 1; l <= M; l++) {
			if (circle[j][l] <= 0) continue;
			
			if (circle[j][l] > avg) {// 크면 1 빼고
				circle[j][l]--;
			} else if (circle[j][l] < avg) {  // 작으면 1 더한다
				circle[j][l]++;
			}
		}
	}
}

정말 단순히 문제에서 시키는대로만 하면 됩니다.
까다로운 구현 사항도 없습니다.

3. 전체 코드

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int[][] circle;
	static boolean[][] erase;
	static boolean isErase = false;
	
	// 인접한 부분이 0이 아니고 같다면 지우는 함수
	static void delete(int y1, int x1, int y2, int x2) {
		if (circle[y1][x1] != 0 
				&&  circle[y2][x2] != 0
				&& circle[y1][x1] == circle[y2][x2]
		) erase[y1][x1] = erase[y2][x2] = isErase = true;
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stk.nextToken());
		int M = Integer.parseInt(stk.nextToken());
		int T = Integer.parseInt(stk.nextToken());
		int[] tmp = new int[M + 1];
		
		circle = new int[N + 2][M + 2]; // 인접 조건 따지기 좋게 크게 잡기
		erase = new boolean[N + 2][M + 2];
		
		for (int i = 1; i <= N; i++) {
			stk = new StringTokenizer(br.readLine());
			
			for (int j = 1; j <= M; j++) {
				circle[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		for (int i = 0; i < T; i++) {
			stk = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(stk.nextToken());
			int d = Integer.parseInt(stk.nextToken());
			int k = Integer.parseInt(stk.nextToken());
			
			// 1. x의 배수인 원판들을 d 방향으로 k칸 회전시킵니다.
			// 방향에 따라 횟수 조정
			k = d == 0 ? k : (M - k); 
			
			// x의 부호인 원판을 d방향으로 k칸 돌리기
			for (int j = x; j <= N; j += x) { 
				for (int l = 1; l <= M; l++) tmp[l] = circle[j][l]; // 해당 원판 복사
				
				for (int l = 1; l <= M; l++) {
					int idx = (l + k) % M;
					idx = idx == 0 ? M : idx;
					
					circle[j][idx] = tmp[l]; // 원판 돌리기
				}
			}
			
			// 계획2 - 원판들의 인접한 좌표들에 대해서 지워줍니다.
			isErase = false;
			
			// 인접한 좌표들에 대하여 지워주기
			for (int j = 1; j <= N; j++) {
				for (int l = 1; l <= M; l++) {
					delete(j - 1, l, j, l);
					delete(j + 1, l, j, l);
					delete(j, l - 1, j, l);
					delete(j, l + 1, j, l);
				}
				
				delete(j, 1, j, M);
			}
			
			// 계획3 - 인접한 수를 지운 여부에 따라 조건대로 구현합니다.
			if (isErase) { // 지워줘야하는 곳이 있다면 지워주기
				for (int j = 1; j <= N; j++) {
					for (int l = 1; l <= M; l++) {
						if (erase[j][l]) {
							circle[j][l] = 0;
						}
						
						erase[j][l] = false;
					}
				}
			} else { // 인접한 곳이 없어 지워진 곳이 없을 때
				double avg = 0;
				int cnt = 0;
				
				for (int j = 1; j <= N; j++) {
					for (int l = 1; l <= M; l++) {
						if (circle[j][l] <= 0) continue;
						avg += circle[j][l];
						cnt++;
					}
				}
				
				// 평균 계산
				avg /= 1.0 * cnt;
				
				for (int j = 1; j <= N; j++) {
					for (int l = 1; l <= M; l++) {
						if (circle[j][l] <= 0) continue;
						
						if (circle[j][l] > avg) {// 크면 1 빼고
							circle[j][l]--;
						} else if (circle[j][l] < avg) {  // 작으면 1 더한다
							circle[j][l]++;
						}
					}
				}
			}
		} 
		
		int ans = 0;
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				ans += circle[i][j];
			}
		}
		
		bw.write(ans + "");
		bw.close();
	}
}