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

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

17822번: 원판 돌리기

 

풀이 방법

시뮬레이션 문제이다.

1. 번호가 x의 배수인 원판을 d방향으로 회전시킨다.
   
   • 임시 배열 tmp를 생성하여 원래의 상태를 복사해놓는다.
   • y번째 수를 k칸 회전시킨 위치의 값을 tmp[y] 값으로 갱신한다.
   • 이때, 시계 방향이면 인덱스가 증가하는 방향이므로 이동한 후의 위치는 (y+k) % M이다.
   • 반시계 방향이면 y-k 해주는 데 이때, 0보다 작아지면 M-abs(y-k) 로 인덱스 범위를 맞춘다.
   • 원판 범위 N을 넘어가지 않을 때까지 x를 계속 더해가며 위 동작을 반복한다.
2. 인접하면서 같은 수를 찾아 지운다.
   • 원판에서 인접하다는 것은 좌표 상에서 상하좌우의 칸과 같다.
   • dfs 로 숫자가 같고 방문하지 않은 인접한 곳이면 flag 를 true로 바꾸고 재귀호출한다.
   • 여기서 flag는 인접하면서 같은 수가 있는지의 여부이다. 하나라도 있으면 true이다.
   • 방문한 곳의 숫자는 0으로 갱신하여 지운다.
   • 모든 탐색이 끝나고 false가 리턴되면 없다는 것이므로 지워진 수를 다시 되살린다.
3. 인접하면서 같은 수가 아무것도 없다면
   • 평균을 구해서 평균보다 큰 수는 -1, 작은 수는 +1한다.
   • 평균 = 원판에 적힌 수 총합 / 적혀있는 수의 개수 (바보같이 원판의 개수로 나누었었다..^^)
   • 평균을 int로 선언하면 소수점이 지워질 것이므로 double 로 선언한다.

 

주의할 점

지워진 값을 0으로 바꾸어 준다면 dfs 로 인접하면서 같은 수를 찾아줄 때와 평균보다 작은 수에 +1 을 해주는 코드에서 꼭 0은 제외해주도록 조건문을 만들어주어야 한다. 처음에 이걸 안해서 지워진 수도 계속 2, 3번 동작에 포함되어 틀렸다..!

 

 

코드

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

public class Main {
    static int N, M, T;
    static int[][] disc;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        disc = new int[N+1][M];

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

        for(int i=0; i<T; i++) {
            st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            spin(X, d, k); // 1. 원판 회전시키기

            // 2-1. 인접하면서 같은 수 찾기
            visited = new boolean[N+1][M];
            boolean flag = false;
            for(int x=1; x<=N; x++) {
                for(int y=0; y<M; y++) {
                    if(!visited[x][y] && disc[x][y] > 0) {
                        int num = disc[x][y];
                        boolean result = dfs(x, y, num);
                        if(result) { // 있다면
                            flag = true;
                        } else {
                            disc[x][y] = num; // 지워진 수 다시 되살리기
                        }
                    }
                }
            }
            // 2-2. 없다면 원판에 적힌 수 평균 구해서 빼고 더하기
            if(!flag) {
                double avg = average();
                for(int x=1; x<=N; x++) {
                    for(int y=0; y<M; y++) {
                        if(disc[x][y] == 0) { // 지워진 수이면 넘어감
                            continue;
                        }
                        if(disc[x][y] > avg) {
                            disc[x][y]--;
                        } else if(disc[x][y] < avg) {
                            disc[x][y]++;
                        }
                    }
                }
            }
        }

        int answer = 0;
        for(int x=1; x<=N; x++) {
            for(int y=0; y<M; y++) {
                answer += disc[x][y];
            }
        }
        System.out.println(answer);
    }

    public static void spin(int x, int d, int k) {

        int cur = x;
        while(cur <= N) {
            // 원래의 상태를 복사
            int[] tmp = new int[M];
            for(int y=0; y<M; y++){
                tmp[y] = disc[cur][y];
            }
            if(d == 0) { // 시계 방향 회전
                for(int y=M-1; y>=0; y--) {
                    disc[cur][(y+k) % M] = tmp[y];
                }
            } else  { // 반시계 방향 회전
                for(int y=0; y<M; y++) {
                    if(y-k >= 0) {
                        disc[cur][y-k] = tmp[y];
                    } else {
                        disc[cur][M-Math.abs(y-k)] = tmp[y];
                    }
                }
            }
            cur += x;
        }
    }

    public static boolean dfs(int x, int y, int num) {
        boolean flag = false; // 인접하면서 같은 수가 있는지의 여부
        visited[x][y] = true;
        disc[x][y] = 0; // 수 지우기

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx > N){ // 원판 범위를 넘어가면
                continue;
            }
            if(ny < 0) {
                ny = M-1;
            } else if(ny >= M) {
                ny = 0;
            }

            if(!visited[nx][ny] && disc[nx][ny] == num) {
                flag = true;
                dfs(nx, ny, num);
            }
        }
        return flag;
    }

    public static double average() {
        double sum = 0;
        int cnt = 0;
        for(int i=1; i<=N; i++) {
            for(int j=0; j<M; j++) {
                if(disc[i][j] > 0) {
                    cnt++;
                }
                sum += disc[i][j];
            }
        }
        return sum / (double)cnt;
    }
}