[backjoon]17822 원판 돌리기 java

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

17822번: 원판 돌리기

원형이라고 해서 겁먹었는데 2차원 배열과 모듈러 연산을 이용해서 풀이하면 쉽게 풀 수 있다.

문제를 살펴보면 구현해야할 것은

1. 원판 이동

-  Queue를 이용해서 이동 하는 칸 수 만큼 모듈러 연산을 이용하여 저장 후 이동시켜주었다. move()

2. 인접한 값들의 확인.

- 원판 이동 후 인접한 값들에 대해 확인하는 것은 일일이 다 비교를 해주었다. 값이 크지 않기 때문에 가능했고, 속도도 그렇게 느리지 않았다. 인접한 값들은 boolean type의 이차원 배열을 이용해서 표시했다.

- 인접한 값들 중에 동일한 값이 없으면 평균을 기준으로 큰 값은 하나 빼고 작은 값은 하나 더하기. 절대절대 비교할 때 소수값을 비교해줘야한다!!!

- 인접한 값들 중에 동일한 값이 있으면 표시한 값들을 확인해가며 제거해준다. 원판위의 값들이 1보다 크다는 것을 이용해서 제거를 0으로 처리하였다.

이렇게 네 가지 정도가 구현 요소라고 생각된다.

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int[][] map;
    static int N, M;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int answer = 0;
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            for (int i = x - 1; i < N; i += x) {
                move(i, d, k);
            }
            // 검증하기
            verify();
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                answer += map[i][j];
            }
        }
        System.out.println(answer);
    }
 
    private static void verify() {
        boolean[][] marked = new boolean[N][M];
        boolean flag = false;
        // 위부터 확인.
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0)
                    continue;
                if (map[i][j] == map[i + 1][j]) {
                    flag = true;
                    marked[i][j] = true;
                    marked[i + 1][j] = true;
                }
            }
        }
        // 아래부터 확인
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0)
                    continue;
                if (map[i][j] == map[i - 1][j]) {
                    flag = true;
                    marked[i][j] = true;
                    marked[i - 1][j] = true;
                }
            }
        }
        // 양 옆 확인
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int col = (j + 1) % M;
                if (map[i][j] == 0)
                    continue;
                if (map[i][j] == map[i][col]) {
                    flag = true;
                    marked[i][j] = true;
                    marked[i][col] = true;
                }
            }
        }
        
        // 반영하기.
        if (!flag) {
            zero();
        } else {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (marked[i][j])
                        map[i][j] = 0;
                }
            }
        }
    }
 
    private static void zero() {
        int cnt = 0;
        int sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0)
                    continue;
                sum += map[i][j];
                cnt++;
            }
        }
        double avg = (double) sum / cnt;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0)
                    continue;
                if (map[i][j] > avg) {
                    map[i][j]--;
                } else if (map[i][j] < avg) {
                    map[i][j]++;
                }
            }
        }
 
    }
 
    private static void move(int i, int d, int k) {
        if (d == 0)
            k *= -1;
        Queue<Integer> queue = new LinkedList<>();
        for (int j = 0; j < M; j++) {
            int col = k + j + M;
            col %= M;
            int cur = map[i][col];
            queue.add(cur);
        }
        for (int j = 0; j < M; j++) {
            map[i][j] = queue.poll();
        }
    }
}