[백준 Baekjoon] 17822번 원판돌리기 - JAVA

[백준 Baekjoon] 17822번 원판 돌리기 - JAVA

---

문제 풀이

구현 및 시뮬레이션 문제입니다. 문제에는 원판이 주어져 보고 어렵다고 생각할 수 있지만 배열과 똑같다고 생각하면 됩니다.

 

입력 받은 원판을 int 2차원 배열로 만들어 저장합니다.

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

 

T번 반복하며 주어진 시뮬레이션 1, 2를 수행합니다.

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());

    rotate(x, d, k);

    if (!erase()) {
        average();
    }
}

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.

public static void rotate(int x, int d, int k) {
    // x의 배수인 원판을 d방향으로 k칸 회전
    for (int i = x; i <= N; i += x) {
        if (d == 0) { // 시계 방향
            for (int t = 0; t < k; t++) { // k칸 회전
                int temp = stencil[i][M]; // swap
                for (int j = M; j > 1; j--) {
                    stencil[i][j] = stencil[i][j - 1];
                }
                stencil[i][1] = temp;
            }
        } else { // 반시계 방향
            for (int t = 0; t < k; t++) { // k칸 회전
                int temp = stencil[i][1]; // swap
                for (int j = 1; j < M; j++) {
                    stencil[i][j] = stencil[i][j + 1];
                }
                stencil[i][M] = temp;
            }

        }
    }
}

2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.

2 - 1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.

public static boolean erase() {
    boolean flag = false; // 인접한 경우 여부
    boolean[][] adjacency = new boolean[N + 1][M + 1];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (stencil[i][j] != 0) {
                // 인접한 원판 검사
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k]; // 검사할 원판
                    int ny = (j + dy[k]) % M; // %연산은 M은 1과 인접

                    // 1번과 N번 원판은 인접한 원판이 없음
                    if (nx < 1 || nx > N) continue;

                    if (ny == 0) ny = M; // 1은 M과 인접

                    // 인접하면서 같은 수를 모두 찾아서 체크
                    if (stencil[i][j] == stencil[nx][ny]) {
                        adjacency[i][j] = adjacency[nx][ny] = flag = true;
                    }
                }
            }
        }
    }

    if (flag) { // 원판에서 인접하면서 같은 수를 지운다.
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (adjacency[i][j]) {
                    stencil[i][j] = 0;
                }
            }
        }

        return true;
    } else {
        return false;
    }
}

2 - 2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

public static boolean erase() {
    boolean flag = false; // 인접한 경우 여부
    boolean[][] adjacency = new boolean[N + 1][M + 1];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (stencil[i][j] != 0) {
                // 인접한 원판 검사
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k]; // 검사할 원판
                    int ny = (j + dy[k]) % M; // %연산은 M은 1과 인접

                    // 1번과 N번 원판은 인접한 원판이 없음
                    if (nx < 1 || nx > N) continue;

                    if (ny == 0) ny = M; // 1은 M과 인접

                    // 인접하면서 같은 수를 모두 찾아서 체크
                    if (stencil[i][j] == stencil[nx][ny]) {
                        adjacency[i][j] = adjacency[nx][ny] = flag = true;
                    }
                }
            }
        }
    }

    if (flag) { // 원판에서 인접하면서 같은 수를 지운다.
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (adjacency[i][j]) {
                    stencil[i][j] = 0;
                }
            }
        }

        return true;
    } else {
        return false;
    }
}

 

소스 코드

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

public class Main {
    public static int N, M;
    public static int[][] stencil;

    public static int[] dx = {1, 0, -1, 0};
    public static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

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

        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());

            rotate(x, d, k);

            if (!erase()) {
                average();
            }
        }

        int answer = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                answer += stencil[i][j];
            }
        }

        System.out.println(answer);
    }

    public static void rotate(int x, int d, int k) {
        // x의 배수인 원판을 d방향으로 k칸 회전
        for (int i = x; i <= N; i += x) {
            if (d == 0) { // 시계 방향
                for (int t = 0; t < k; t++) { // k칸 회전
                    int temp = stencil[i][M]; // swap
                    for (int j = M; j > 1; j--) {
                        stencil[i][j] = stencil[i][j - 1];
                    }
                    stencil[i][1] = temp;
                }
            } else { // 반시계 방향
                for (int t = 0; t < k; t++) { // k칸 회전
                    int temp = stencil[i][1]; // swap
                    for (int j = 1; j < M; j++) {
                        stencil[i][j] = stencil[i][j + 1];
                    }
                    stencil[i][M] = temp;
                }

            }
        }
    }

    public static boolean erase() {
        boolean flag = false; // 인접한 경우 여부
        boolean[][] adjacency = new boolean[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (stencil[i][j] != 0) {
                    // 인접한 원판 검사
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k]; // 검사할 원판
                        int ny = (j + dy[k]) % M; // %연산은 M은 1과 인접

                        // 1번과 N번 원판은 인접한 원판이 없음
                        if (nx < 1 || nx > N) continue;

                        if (ny == 0) ny = M; // 1은 M과 인접

                        // 인접하면서 같은 수를 모두 찾아서 체크
                        if (stencil[i][j] == stencil[nx][ny]) {
                            adjacency[i][j] = adjacency[nx][ny] = flag = true;
                        }
                    }
                }
            }
        }

        if (flag) { // 원판에서 인접하면서 같은 수를 지운다.
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (adjacency[i][j]) {
                        stencil[i][j] = 0;
                    }
                }
            }

            return true;
        } else {
            return false;
        }
    }

    public static void average() {
        int sum = 0, cnt = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 지워진 수는 원판에 적힌 수 갯수 카운트하면 안됨
                if (stencil[i][j] != 0) {
                    sum += stencil[i][j];
                    cnt++;
                }
            }
        }

        double avg = ((double) sum) / cnt; // 평균

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 지워진 수는 건너뛴다.
                if (stencil[i][j] != 0) {
                    if (stencil[i][j] > avg) { // 평균보다 큰 수
                        stencil[i][j]--;
                    } else if (stencil[i][j] < avg) { // 작은 수
                        stencil[i][j]++;
                    }
                }
            }
        }
    }
}