백준 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;
}
}
}
}
}
Author And Source
이 문제에 관하여(백준 17822번: 원판 돌리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-17822번-원판-돌리기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)