백준 - 17822 원판 돌리기

구현 문제입니다.

 

1. 문제 설명

원판과 조건이 주어지고, 조건처럼 행동했을 때 원판에 남아있는 수의 총합을 구하는 문제입니다.

 

원판과 그에 인접한 위치를 이차원 배열 그림으로 나타내면 아래와 같습니다.

기본적으로 4방 탐색을 하면서

세로는 위아래 끝이 연결되지 않습니다.

가로는 양옆 끝이 연결되어 있습니다.

 

 

또, 원판이 회전하게 되면 가로의 방향으로 만 움직입니다.

 

D가 0일때는 아래와 같이 오른쪽(시계 방향)으로 움직입니다.

 

D가 1일때는 아래와 같이 왼쪽(반시계 방향)으로 움직입니다.

 

X는 회전할 세로 위치를 의미하며,

K는 회전의 양을 의미합니다.

 

2. 접근 방법

접근 방법은 문제 자체에서 주어진 그 순서와 크게 다르지 않습니다.

1.  x의 배수의 위치의 배열들을 회전한다.
   1. d가 0일경우 오른쪽(시계 방향)으로 회전한다.
   2. d가 1일경우 왼쪽(반시계 방향)으로 회전한다.
   3. 회전할 때 좌 우측의 끝은 반대로 이동한다. (원형)
2. 순차적으로 인접한 숫자와 '0'을 확인한다.
   1. '0'을 제외한 일치하는 숫자가 있으면 그 위치를 저장한다.
   2. 모든 숫자가 '0'인지도 확인한다.
3. 원판의 특정 위치의 수와 인접하면서 일치하는 수가 있는 경우 둘 다 삭제한다.
   1. 인접하는 수와 전부 일치하지 않는다면 평균을 구해서 평균보다 크면 +1을 하고, 작으면 -1을 한다. 
   2. 만약 모든 숫자가 0이면 더이상 진행할 필요가 없어 모든 반복을 종료하게 한다.

 

[구현 코드]

import java.io.*;
import java.util.*;

public class Main {

    private static final int[] DX = {-1, 1, 0, 0};
    private static final int[] DY = {0, 0, -1, 1};

    private static int n, m, t, sum, cnt;
    private static int[][] roundMap;
    private static boolean isAllZero, isFind;

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

        init(br, stz);

        isAllZero = false;
        for (int i = 0; i < t; i++) {
            stz = new StringTokenizer(br.readLine());

            if (isAllZero) continue;
            isAllZero = true;

            int x = Integer.parseInt(stz.nextToken()) - 1; // 배수로 동작 (+2);
            int d = Integer.parseInt(stz.nextToken()); // 0 : 시계, 1 : 반시계
            int k = Integer.parseInt(stz.nextToken()); // 횟수 < m

            // 1. x의 배수의 위치의 배열들을 회전한다.
            rotateRoundMap(x, d, k);

            sum = 0;
            cnt = 0;
            isFind = false;
            boolean[][] isDelete = new boolean[n][m];
            // 2. 순차적으로 인접한 숫자와 '0'을 확인한다.
            checkAroundNumberInRoundMap(isDelete);

            // 3.2 만약 모든 숫자가 0이면 더이상 진행할 필요가 없어 모든 반복을 종료하게 한다.
            if (isAllZero) continue;

            if (isFind) {
                // 3. 원판의 특정 위치의 수와 인접하면서 일치하는 수가 있는 경우 둘 다 삭제한다.
                setNumberToZero(isDelete);
            } else {
                // 3.2 인접하는 수와 전부 일치하지 않는다면 평균을 구해서 평균보다 크면 +1을 하고, 작으면 -1을 한다.
                numberReAllocate(sum, cnt);
            }
        }

        int total = getTotal();

        bw.write(String.valueOf(total));

        bw.flush();
        bw.close();
        br.close();
    }

    private static void init(BufferedReader br, StringTokenizer stz) throws IOException {
        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());
        t = Integer.parseInt(stz.nextToken());

        roundMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            stz = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                roundMap[i][j] = Integer.parseInt(stz.nextToken());
            }
        }
    }

    private static void checkAroundNumberInRoundMap(boolean[][] isDelete) {
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {

                if (roundMap[r][c] == 0) continue;
                isAllZero = false; // 2.2 모든 숫자가 '0'인지도 확인한다.
                sum += roundMap[r][c];
                cnt++;

                for (int e = 0; e < 4; e++) {
                    int nx = r + DX[e];
                    int ny = relocate(c + DY[e], m);

                    if(nx < 0 || nx >= n) continue;

                    // 2.1 '0'을 제외한 일치하는 숫자가 있으면 그 위치를 저장한다.
                    if (roundMap[r][c] == roundMap[nx][ny]) {
                        isDelete[nx][ny] = true;
                        isFind = true;
                    }
                }
            }
        }
    }

    private static void setNumberToZero(boolean[][] isDelete) {
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (isDelete[r][c]) {
                    roundMap[r][c] = 0;
                }
            }
        }
    }

    private static void rotateRoundMap(int x, int d, int k) {
        for (int r = x; r < n; r += (x +1)) {
            Deque<Integer> qu = new LinkedList<>();
            for (int c = 0; c < m; c++) {
                qu.add(roundMap[r][c]);
            }

            int c = k;
            while (c-- > 0) {
                Integer el;
                if (d == 0) {
                    // 1.1 d가 0일경우 오른쪽(시계 방향)으로 회전한다.
                    el = qu.pollLast();
                    qu.addFirst(el);
                } else {
                    // 1.2 d가 1일경우 왼쪽(반시계 방향)으로 회전한다.
                    el = qu.pollFirst();
                    qu.addLast(el);
                }
            }

            for (int t = 0; t < m; t++) {
                roundMap[r][t] = qu.poll();
            }
        }
    }

    private static int relocate(int q, int len){
        if(q < 0){
            q = len-1;
        }else if(q == len){
            q  = 0;
        }
        return q;
    }

    private static void numberReAllocate(double sum, int cnt) {
        double avg = (sum / cnt);

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (roundMap[r][c] == 0) continue;

                if (roundMap[r][c] > avg) {
                    roundMap[r][c]--;
                } else if (roundMap[r][c] < avg) {
                    roundMap[r][c]++;
                }
            }
        }
    }

    private static int getTotal() {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sum += roundMap[i][j];
            }
        }
        return sum;
    }
}