백준 17822번: 원판 돌리기

문제 설명

• https://www.acmicpc.net/problem/17822
• 특정 원판들을 회전합니다.
• 회전 후 인접하면서 같은 수를 제거합니다.
• 인접하면서 같은 수가 하나도 없다면 평균보다 높은 수는 1을 빼고 평균보다 낮은 수는 1을 더합니다.

접근법

• 1차원 배열의 회전으로 원판을 돌립니다.
• BFS를 통해 인접하면서 같은 수를 제거합니다. 이때 평소의 BFS와 달리 다음을 유의해야 합니다.
  • 원이기 때문에 board[i][0]과 board[i][M]은 인접한 걸로 처리해야 합니다.
  • 짝이 존재할 경우에만 제거할 수 있습니다.
    • 큐에서 꺼낼 때 0으로 변경하는 게 아니라 같은 값이 존재할 때 0으로 바꿔줘야 합니다.

pseudocode

main(){
	for(T번){
    	TurnTable // 회전
        BFS // 같은 값 제거
        if(같은 값을 하나도 제거하지 못했으면){
        	평균보다 낮은 숫자는 +1, 평균보다 높은 숫자는 -1
        }
    }
}

BFS(start){
	num = start좌표의 숫자
	q.add(start)
	while(q가 빌 때까지){
    	for(4방탐색을 진행){
        	원형이기 때문에 arr[x][0]에서 한 칸 왼쪽은 arr[x][M-1]
            원형이기 때문에 arr[x][M-1]에서 한 칸 오른쪽은 arr[x][0]
            if(board위에 있고 num과 같은 숫자라면){
            	q에 {nx,ny}삽입
                똑같은 값을 제거(0으로 표시)
            }
        }
    }
}

정답

import java.util.*;

class Main {
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int N, M;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int T = sc.nextInt();
		int[][] board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}

		for (int t = 0; t < T; t++) {
			int x = sc.nextInt();
			int d = sc.nextInt();
			int k = sc.nextInt();

			// x의 배수인 행들을 돌립니다.
			for (int i = 0; i < N; i++) {
				if ((i + 1) % x != 0) continue;
				board[i] = TurnTable(board[i], d, k);
			}

			
			int BZeroCnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] == 0) {
						BZeroCnt++;
					} else {
						int[] temp = { i, j };
						BFS(temp, board); // 모든 좌표에 대해 BFS를 실행합니다.
					}
				}
			}

			int AZeroCnt = 0;
			int Sum = 0;
			int Cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] == 0) {
						AZeroCnt++;
					} else {
						Sum += board[i][j];
						Cnt++;
					}
				}
			}
			
			// BFS를 시도하기 이전의 0의 개수와 시도한 후 0의 개수가 같다는 건 아무런 제거가 없었다는 의미입니다.
			if (BZeroCnt == AZeroCnt) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if (board[i][j] == 0) continue;
						double a = 1.0 * Sum / Cnt;
						if (1.0 * board[i][j] > a) {
							board[i][j]--;
						} else if (1.0 * board[i][j] < a) {
							board[i][j]++;
						}
					}
				}
			}

		}
		int ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				ans += board[i][j];
			}
		}

		System.out.println(ans);
	}

	public static int[] TurnTable(int[] arr, int d, int k) {
		int size = arr.length;
		int[] newArr = new int[size];

		if (d == 0) { // 시계방향으로 회전합니다.
			for (int i = 0; i < newArr.length; i++) {
				newArr[i] = arr[(size + i - k) % size];
			}
		} else { // 반시계방향으로 회전합니다.
			for (int i = 0; i < newArr.length; i++) {
				newArr[i] = arr[(i + k) % size];
			}

		}
		return newArr;
	}

	public static void BFS(int[] start, int[][] board) {
		int num = board[start[0]][start[1]]; 
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);		
		while (!q.isEmpty()) {
			int[] temp = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = temp[0] + dx[d];
				int ny = temp[1] + dy[d];
				// 행 데이터에 대해 원형인 걸 처리해줍니다.
				if (ny == -1) ny = M - 1;
				if (ny == M) ny = 0;
				
				if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == num) { 
					int[] temp2 = { nx, ny };
					q.add(temp2);
					// 짝이 존재해야 0으로 제거가 가능합니다.
					board[temp[0]][temp[1]] = 0;
					board[nx][ny] = 0;
				}
			}
		}
	}

}