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

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

17822번: 원판 돌리기

 

난이도 : 골드 3

 

단순 구현 문제입니다.

톱니바퀴가 생각나는 문제였습니다.

2020/08/15 - [문제풀이/자바] - [백준 15662] 톱니바퀴(2) (자바)

[백준 15662] 톱니바퀴(2) (자바)

 

각 원판을 ArrayList를 통해 표현했습니다. 

회전 후 인접하며 수가 같은 경우, 같은 수가 없는 경우로 나눠서 구현했습니다.

• 인접하며 수가 같은 경우 : DFS로 같은 수 모두 제거
• 같은 수가 없는 경우 : 남은 수의 평균을 구하고 +1, -1 작업을 해줍니다.

단계별로 나눠 생각하며 구현을 하면 무난히 풀 수 있었습니다.

---

전역 변수 

n = 원판의 수

m = 한 원판에 적힌 수의 개수

t = 동작 횟수

change = 인접한 수가 있는지 없는지 확인을 위한 변수

dx, dy = DFS를 위해 이용할 배열

메소드

void main 

입력을 받고 t번 동작합니다. 동작은 명령어를 읽고 회전, 인접수 검사, 없을 시 계산입니다.

(rotate, check, cal, sum 호출)

 

void rotate

x 배수의 원판을 d방향으로 k번 회전합니다.

회전에 대한 자세한 설명은 위의 톱니바퀴에서 했으므로 생략하겠습니다.

d == 0 ? 시계 방향 : 반시계 방향

 

void check

인접한 수(원판 위, 아래, 같은 원판에서의 양 옆)를 모두 제거합니다. 제거한 수는 -1로 표시합니다.

원판은 원형이므로 인덱스를 벗어나면 반대편으로 이동시켜줍니다.

x는 원판의 층, y는 원판에서의 인덱스입니다. 재귀를 통한 DFS로 모두 제거합니다.

 

int sum

정답 출력을 위한 메소드입니다. 모든 원판에서의 남은 값을 더해 반환합니다.

 

void cal

인접한 수의 제거가 없었던 경우 실행됩니다.

모든 원판의 평균을 구합니다. 만약 남은 수가 없을 경우에 divide 0 에러가 발생하므로 return 해줍니다.

평균을 구하고 보다 큰 수에서는 -1, 작은 수에서는 +1을 해줍니다.

 

boolean check

원판의 층이 정상 값인지 확인합니다. 1층~ n층까지 존재합니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class p17822 {
    
    static int n, m, t;
    static ArrayList<Integer> al[];
    static boolean change;
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());
        t = Integer.parseInt(stz.nextToken());
        al = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            al[i] = new ArrayList<Integer>();
            stz = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++)
                al[i].add(Integer.parseInt(stz.nextToken()));
        }
        
        for(int i = 0; i < t; i++){
            stz = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(stz.nextToken());
            int d = Integer.parseInt(stz.nextToken());
            int k = Integer.parseInt(stz.nextToken());
            change = false;
            rotate(x, d, k);
            for(int a = 1; a <= n; a++){
                for(int b = 0; b < m; b++)
                    if(al[a].get(b) != -1)
                        check(a, b, al[a].get(b));
            }
            
            if(!change)
                cal();
        }
        System.out.println(sum());
    }
    
    public static void rotate(int x, int d, int k) {
        for(int i = 1; i <= n; i++) {
            if(i % x == 0) {
                if(d == 0) {
                    for(int j = 0; j < k; j++)
                        al[i].add(0, al[i].remove(al[i].size()-1));
                }
                else{
                    for(int j = 0; j < k; j++){
                        int number = al[i].remove(0);
                        al[i].add(al[i].size(), number);
                    }
                }
            }
        }
    }
    
    public static void check(int x, int y, int value) {
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(ny == m)
                ny = 0;
            if(ny == -1)
                ny = m-1;
            
            if(check(nx) && al[nx].get(ny) == value && al[nx].get(ny) != -1) {
                al[nx].set(ny, -1);
                change = true;
                check(nx, ny, value);
            }
        }
    }
    
    public static int sum() {
        int sum = 0;
        for(int a = 1; a <= n; a++){
            for(int b = 0; b < m; b++)
                if(al[a].get(b) != -1)
                    sum += al[a].get(b);
        }
        
        return sum;
    }
    
    public static void cal() {
        int sum = 0;
        int count = 0;
        for(int a = 1; a <= n; a++){
            for(int b = 0; b < m; b++)
                if(al[a].get(b) != -1) {
                    sum += al[a].get(b);
                    count++;
                }
        }
        if(count == 0)
            return;
        double avg = (double) sum / count;
        for(int a = 1; a <= n; a++){
            for(int b = 0; b < m; b++) {
                if(al[a].get(b) != -1) {
                    if(al[a].get(b) > avg)
                        al[a].set(b, al[a].get(b) - 1);
                    else
                        if(al[a].get(b) < avg)
                            al[a].set(b, al[a].get(b) + 1);
                }
            }
        }
    }
    
    public static boolean check(int x) {
        return x >= 1 && x <= n;
    }
    
}