백준 : 17822 JAVA

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

17822번: 원판 돌리기

글에 대한 설명이 턱없이 부족하다. 문제를 풀면서 테스트 케이스를 돌려보면서 확인해야한다.

 

1. 원판은 시작할때는 인접한 것을 check하지 않는다. 시작하자마자 인접하는 것을 지우고 돌리면 예제 case가 나오지 않는다.

 

2. 돌리고 나서 인접한 case가 없다면 아무것도 지우지 않게되는데 이때 합을구하고 평균을 내는데 평균은

전체 원판의 수가아닌 활성화된 원판의 수를 의미한다.

 

3. 평균에서 같은 값은 아무 처리하지 않는다.

 

4. 시간을 올리게 하기 위해선 돌아간 원판의 위치에서 같은 인자값을 해줘도된다 (소스에서는 처리하지않음)

 

 

문제를 풀때는 2차원 배열로 원판을 구현하고 배열 좌우는 연결되있다고 가정한다. LinkedList보단 배열의 인자값을 M일때 0으로 처리해주는게 훨씬 편하다.

 

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B17822 {
    static int N, M, T;
    static int[][] One;
    static int[][] Seq;
    static int[] dy = { 0, 0, 1, -1 };
    static int[] dx = { 1, -1, 0, 0 };
    static boolean check;
    static boolean[][] checkMap;
 
    public static void main(String[] args) throws IOException {
        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());
        T = Integer.parseInt(st.nextToken());
 
        One = new int[N][M];
        Seq = new int[T][3];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                One[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                Seq[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // RotateGo
        for (int t = 0; t < T; t++) {
            int x = Seq[t][0];
            int d = Seq[t][1];
            int k = Seq[t][2];
            // 배수들은 다회전 시키기 0 :시계 1:반시계
 
            for (int i = x - 1; i < N; i += x) {
                Rotate(i, d, k);
 
            }
 
            // 인접한게 있나? 있으면 지우기
            check = false;
            checkMap = new boolean[N][M];
            for (int i = 0; i < N; i++) {
                OneCheck(i);
            }
            if (!check) {
                // 평균을 구하고
                // 인접한게 하나도 없으면 sum -1 sum+1
                isNot();
            }
        }
 
 
        // 모든 원판의 합
        System.out.println(Answer());
    }
 
    public static void Rotate(int x, int d, int k) {
        k %= M;
        if (k == 0)
            return;
 
        // 반시계방향 k번 회전은
        // 시계방향 M-k 번 회전과 같다
        if (d == 0) {
            // 시계 방향
            for (int kk = 0; kk < k; kk++) {
 
                int tmp = One[x][M - 1];
                for (int i = M - 1; i >= 1; i--) {
                    One[x][i] = One[x][i - 1];
                }
                One[x][0] = tmp;
            }
 
        } else {
            for (int kk = 0; kk < M - k; kk++) {
 
                int tmp = One[x][M - 1];
                for (int i = M - 1; i >= 1; i--) {
                    One[x][i] = One[x][i - 1];
                }
                One[x][0] = tmp;
            }
 
        }
    }
 
    // 원판 check
    public static void OneCheck(int x) {
        for (int j = 0; j < M; j++) {
            if (One[x][j] == 0 || checkMap[x][j])
                continue;
            // 좌우밑왼 check
            int ny, nx;
            for (int d = 0; d < 4; d++) {
                ny = x + dy[d];
                nx = j + dx[d];
 
                if (ny < 0 || ny >= N)
                    continue;
 
                if (nx == -1)
                    nx = M - 1;
                else if (nx == M)
                    nx = 0;
 
                if (One[x][j] == One[ny][nx]) {
                    DFS(x, j, One[x][j]);
                    check = true;
                }
            }
 
        }
    }
 
    // 원판 돌면서 같은값 0으로 초기화 하기
    public static void DFS(int y, int x, int eraser) {
        int ny;
        int nx;
 
        if (checkMap[y][x])
            return;
        if (One[y][x] == 0)
            return;
 
        if (One[y][x] == eraser) {
            One[y][x] = 0;
            checkMap[y][x] = true;
        }
 
        for (int d = 0; d < 4; d++) {
            ny = y + dy[d];
            nx = x + dx[d];
 
            if (ny < 0 || ny >= N)
                continue;
 
            if (nx == -1)
                nx = M - 1;
            else if (nx == M)
                nx = 0;
 
            if (One[ny][nx] == 0)
                continue;
 
            if (One[ny][nx] == eraser) {
                if (!checkMap[ny][nx]) {
                    DFS(ny, nx, eraser);
                }
            }
        }
    }
 
    public static void isNot() {
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (One[i][j] == 0)
                    continue;
                cnt++;
                sum += One[i][j];
            }
        }
 
        double avg = (double) sum / (cnt);
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (One[i][j] == 0)
                    continue;
 
                if (One[i][j] > avg) {
                    One[i][j] += -1;
                } else if(One[i][j] < avg){
                    One[i][j] += 1;
                }
            }
        }
 
    }
 
    public static int Answer() {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sum += One[i][j];
            }
        }
 
        return sum;
    }
 
}