[ 백준 / BOJ 17822 ] 원판 돌리기 ( 자바 / JAVA )

https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

문제설명

반지름이 1,2,...,N인 원판이 크기가 작아지는 순이고, 중심이 모두 같음
반지름이 i이면 i번째 원판
각각의 원판에는 M개의 정수가 존재, (i,j) 👉 i번째 원판에 적힌 j번째 수의 위치

• (i,1)은 (i,2), (i,M)과 인접
• (i,M)은 (i,1), (i,M-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)

각 원판의 회전은 독립적으로 진행됨

총 T번 회전, i번째 회전할 때 사용되는 변수는 $x_i, d_i, k_i$

1. 번호가 $x_i$의 배수인 원판을 $d_i$방향으로 $k_i$칸 회전
   • $d_i$ == 0 👉 시계 방향
   • $d_i$ == 1 👉 반시계 방향
2. 원판에 수가 남아있으면, 인접하면서 같은 수를 모두 찾음
   1) 인접하고 같은 수가 없다면

    - 존재하는 수의 평균을 구하고, 평균보다 큰 수 -= 1, 평균보다 작은 수 += 1

   2) 있다면, 찾은 수를 모두 지움

T번 회전 후, 원판에 적힌 수의 합을 출력

 

문제풀이

disc[N+1][M] : 1번 원판 ~ N번 원판의 각 숫자들이 저장된 배열

1) 회전

rotateDisc(x, d, k)
int dir = d == 0 ? 1 : -1;
↑ 반시계 방향이라면 앞으로 이동, 시계방향이라면 뒤로 이동이기때문에

임의의 배열 tmp에 이동결과 저장
tmp[j + (dir * (k % M)) + M) % M] = disc[i][j];

그 후, 원래 배열 disc에 저장

2) 인접한 같은 숫자 존재 확인

disc내의 0이 아닌 모든 수에 대해
BFS 이용해서 같은 값 찾기

행 인덱스에 대해서는 0 < nx <= N인 부분만 진행,
열 인덱스에 대해서는

1) if(ny == M) ny = 0;
2) if(ny == -1) ny = M-1;
로 변경해줌

Boolean isSame 👉 그 값에 대해서 변경하기 위한 변수
Boolean isChange 👉 전체 확인 후, 인접한 같은 값 삭제 확인 위한 변수

3) 평균 구하고 숫자 변경

만약 위의 isChange 변수가 false라면,
평균을 구하기 👉 calAverage()
그 후, 평균값에 따라 숫자 변경 👉 changeNum(float sum)

3) 모든 원판의 숫자 합 출력

 

코드

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

public class Main_BOJ_17822_원판_돌리기 {

    static int N, M, T, x, d, k;
    static int[][] disc;
    static boolean[][] isVisited;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static boolean isSame, isChange = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        T = Integer.parseInt(stringTokenizer.nextToken());

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

        while (T-- > 0) {
            stringTokenizer = new StringTokenizer(br.readLine());
            x = Integer.parseInt(stringTokenizer.nextToken());
            d = Integer.parseInt(stringTokenizer.nextToken());
            k = Integer.parseInt(stringTokenizer.nextToken());

            rotateDisc(x, d, k);
//            System.out.println("x : " +x +" d: " + d +" k: " +k );
//            tostring();
            isChange = false;
            for (int i = 1; i <= N; i++) {
                for (int j = 0; j < M; j++) {
                    isSame = false;
                    if(disc[i][j] != 0) {
                        checkAdjNum(i, j, disc[i][j]);
                        if(isSame) {
                            disc[i][j] = 0;
/*                            System.out.println("i : "+i+" j : "+j );
                            tostring();*/
                        }
                    }
                }
            }

            if (!isChange) {
                calAverage();
            }
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < M; j++) {
                ans += disc[i][j];
            }
        }
        System.out.println(ans);
    }

    private static void tostring() {
        for (int[] di : disc) {
            for (int d : di) {
                System.out.print(d + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private static void calAverage() {
//        System.out.println("calAverage()");
        float sum = 0;
        float cnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < M; j++) {
                sum += disc[i][j];
                if(disc[i][j] != 0) cnt += 1;
            }
        }

        sum /= cnt;
        changeNum(sum);
    }

    private static void changeNum(float sum) {
//        System.out.println("sum: " + sum);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < M; j++) {
                if(disc[i][j] != 0){
                    if(disc[i][j] < sum) disc[i][j] += 1;
                    else if(disc[i][j] > sum) disc[i][j] -= 1;
                }
            }
        }
//        tostring();
    }

    private static void checkAdjNum(int x, int y, int value) {
        isVisited = new boolean[N + 1][M];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        isVisited[x][y] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if(ny == M) ny = 0;
                if(ny == -1) ny = M - 1;

                if(nx <= 0 || N < nx || isVisited[nx][ny] || disc[nx][ny] != value) continue;

                q.add(new int[]{nx, ny});
                isVisited[nx][ny] = true;
                disc[nx][ny] = 0;
                isSame = true;
                isChange = true;
            }
        }

    }

    private static void rotateDisc(int x, int d, int k) {
        // 회전
        int dir = d == 0 ? 1 : -1;
        for (int i = x; i < N + 1; i += x) {
            int[] tmp = new int[M];
            for (int j = 0; j < M; j++) {
                tmp[(j + (dir * (k % M)) + M) % M] = disc[i][j];

            }
            disc[i] = Arrays.copyOf(tmp, M);
        }
    }
}