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

문제 링크 : https://www.acmicpc.net/problem/17822

이 문제는 구현 문제입니다. 문제의 조건대로 하나하나 구현해나가면 풀 수 있습니다.

이 문제의 핵심 풀이법은 원판을 이차원 배열로 변형하여 푸는 것입니다. 각 행을 하나의 원판으로 보면 한 좌표를 기준으로 상하좌우 값이 인접한 숫자가 됩니다. 여기서 주의할 점은 원판이기 때문에 가로값의 경우 시작과 끝이 이어져 있기 때문에 좌표가 이차원 배열을 벗어난다면 각각 처음과 끝으로 좌표를 재설정해주어야 합니다. 세로값은 이어져 있지 않기 때문에 이 부분 역시 주의하셔야 합니다.

이 문제를 풀었을 때 사소한 부분에 대해서 잘못 접근해서 시간 소모가 컸습니다. 문제의 테스트 케이스는 모두 만족했으나 답이 틀린 경우입니다. 우선 평균을 구하기 위해 미리 총합을 구하고 값을 빼는 방식으로 접근하게 될 경우 답이 틀립니다. 또한 인접한 숫자들을 판단하는 함수를 boolean으로 처리하는 방식으로 접근할 경우 역시 답이 틀립니다. 이 방식 말고 총합은 직접 이중 반복문을 통해 구하여 평균을 구하고, 인접한 숫자 여부를 static 변수로 설정해서 참조하는 방식으로 접근하면 풀 수 있습니다.

다음은 코드입니다.

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

public class Main{
    static int N,M,T;
    static boolean isSameNumExist = false;
    // 조건에서 (i, j)는 (i-1, j), (i+1, j)와 인접하다고 했기 때문에 이차원 배열로 설정 후
    // 각 행을 회전시킨 후 상하좌우 인접한 숫자를 확인하면 됨
    static int[][] req = new int[51][51];
    static int[] dy = {1,0,-1,0};
    static int[] dx = {0,1,0,-1};

    // dfs
    static void checkPlate(int y, int x, int value){
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            // 원판이므로 범위 밖으로 나갔을 경우 반대쪽 끝 값으로 매칭
            if(nx<0) nx = M-1;
            else if(nx>=M) nx = 0;
            else if(ny<0 || ny>=N) continue;

            // 인접값이 비교값과 같을 경우 값 초기화 후 dfs 실행
            if(req[ny][nx] == value){
                isSameNumExist = true;
                req[ny][nx] = 0;
                checkPlate(ny,nx,value);
            }
        }
    }

    static void rotate(int i, int d, int k){
        // 시계 방향 회전 = 맨 끝 값은 맨 앞으로, j++
        if(d == 0){
            // k번 회전
            for(int n=0;n<k;n++){
                int t1 = req[i][M-1];
                for(int j=0;j<M;j++){
                    int t2 = req[i][j];
                    req[i][j] = t1;
                    t1 = t2;
                }
            }
        }
        // 시계 반대 방향 회전 = 맨 처음 값은 맨 끝으로, j--
        else if(d == 1){
            // k번 회전
            for(int n=0;n<k;n++){
                int t1 = req[i][0];
                for(int j=M-1;j>=0;j--){
                    int t2 = req[i][j];
                    req[i][j] = t1;
                    t1 = t2;
                }
            }
        }

    }

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

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                req[i][j] = Integer.parseInt(st.nextToken());
                // 만약 총합을 미리 구하고 빼는 식으로 진행하면 답이 틀림
            }
        }

        // T 수만큼 회전 명령 실행
        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());

            // 번호가 x의 배수인 원판이라면 d 방향으로 k칸 회전
            for(int i=0;i<N;i++){
                if((i+1)%x == 0) rotate(i,d,k);
            }

            // 인접한 수가 같은 것들을 모두 찾음
            boolean isExist = false;
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    isSameNumExist = false;
                    // 현재 수 체크
                    // 이 때 checkPlate 함수를 boolean으로 내보내면 틀림
                    if(req[i][j] != 0) checkPlate(i,j,req[i][j]);
                    // 인접하면서 수가 같은 것들이 있을 경우 삭제
                    if(isSameNumExist){
                        isExist = true;
                        req[i][j] = 0;
                    }
                }
            }

            // 인접하면서 같은 수가 없을 경우
            if(!isExist){
                double sum = 0;
                int num = 0;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (req[i][j] != 0) {
                            sum += req[i][j];
                            num++;
                        }
                    }
                }
                double avg = sum/num;

                // 평균보다 큰 수에서 1을 빼고 작은 수에 1을 더함
                for(int i=0;i<N;i++){
                    for(int j=0;j<M;j++){
                        if(req[i][j] != 0){
                            if(avg > req[i][j]) req[i][j]++;
                            else if(avg < req[i][j]) req[i][j]--;
                        }
                    }
                }
            }
        }

        // 원판에 적힌 수의 합 출력
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                res += req[i][j];
            }
        }
        System.out.println(res);
    }
}