[Algorithm] SW 기출문제 - 원판 돌리기(17822) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 원판 돌리기 자바 풀이를 작성하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int t = parseInt(st.nextToken());
        
        Board board = new Board(n, m);
        
        for (int row = 1; row <= n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= m; col++) {
                board.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int x = parseInt(st.nextToken()); // 배수 행
            int dir = parseInt(st.nextToken()); // 방향
            int k = parseInt(st.nextToken()); // 칸 수
            board.rotate(x, dir, k);
        }
        
        System.out.println(board.getSum());
    }
}

class Board {
    int n; // 행의 개수
    int m; // 열의 개수
    int[][] map;
    int[] tmp; // 임시 swap 배열
    
    Board(int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n + 1][m + 1];
        tmp = new int[m + 1];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }
    
    // dir -> 시계: 0, 반시계: 1
    void rotate(int x, int dir, int k) { // x는 row 배수 형태로
        for (int row = 1; row <= n; row++) {
            if (row % x == 0) { // x의 배수
                swap(map[row], k, dir);
            }
        }

        int leftCol; // 인접한 왼쪽 열
        int rightCol; // 인접한 오른쪽 열
        
        int totalSum = 0; // 총 합
        int totalCnt = 0; // 총 개수
        List<Point> zeros = new ArrayList<>(); // zero가 되는 포인트
        
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) {
                int flag = zeros.size(); // zeros.size가 변한다면 인접한 것이 있다는 의미
                int nowValue = map[row][col];

                if (nowValue == 0) continue; // 만약 현재 값이 0인 것은 건너뛰기

                totalSum += nowValue;
                totalCnt++;
                
                if (col == 1) { // 맨 좌측 열은 맨 우측 열 인접하도록 설정하기
                    leftCol = m;
                    rightCol = col + 1; 
                } else if (col == m) {
                    leftCol = m - 1;
                    rightCol = 1;
                } else { // 나머지는 양쪽 열
                    leftCol = col - 1;
                    rightCol = col + 1;
                } 
                
                if (map[row][leftCol] == nowValue) {
                    zeros.add(new Point(row, leftCol));
                }
                
                if (map[row][rightCol] == nowValue) {
                    zeros.add(new Point(row, rightCol));
                }
                
                if (row == 1) { // 맨 윗행은 인접한 행이 바로 아래 행
                    if (nowValue == map[row + 1][col]) zeros.add(new Point(row + 1, col));
                } 
                else if (row == n) { // 맨 아래 행의 인접한 행은 바로 윗행
                    if (nowValue == map[row - 1][col]) zeros.add(new Point(row - 1, col));
                } 
                else {
                    if (nowValue == map[row + 1][col]) zeros.add(new Point(row + 1, col));
                    if (nowValue == map[row - 1][col]) zeros.add(new Point(row - 1, col));
                }

                if (zeros.size() != flag) zeros.add(new Point(row, col)); // 값이 추가되었다는 것을 의미하므로 자신도 추가하기
            }

        }
        
        if (!zeros.isEmpty()) {
            for (Point p : zeros) {
                map[p.row][p.col] = 0; // 인접하여 같은 값도 zero 설정
            }
        } 
        else { // 한 번도 인접한 값이 같은 것이 없음
            if (totalCnt != 0) {
                double avg = (double) totalSum / totalCnt;
                
                for (int row = 1; row <= n; row++) {
                    for (int col = 1; col <= m; col++) {
                        int nowValue = map[row][col];
                        if (nowValue != 0 && avg < nowValue) map[row][col]--; // 평균보다 크다면 --
                        else if (nowValue != 0 && avg > nowValue) map[row][col]++; // 평균보다 작다면 ++
                    }
                }
            }
        }
    }
    
    int getSum() {
        int sum = 0;
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) sum += map[row][col];
        }
        return sum;
    }

    // 0, 1, 2, 3, 4, 5
    // k만큼 시계 방향 회전 i + k를 하되, 인덱스를 벗어난 경우 m 빼기
    // i = 2, k = 3 => tmp[5] = 2;
    // i = 3, k = 3 => tmp[6 - 5] = 3;
    void swap(int[] arr, int k, int clockWise) { // k 만큼 스왑
        if(clockWise == 0) {    // 시계 방향 회전
            for (int i = 1; i <= m; i++) {
                int next = i + k > m ? i + k - m : i + k;
                tmp[next] = arr[i];
            }
        }

        // 반시계는 왼쪽으로 칸을 옮기되 0보다 작아질 수 있으므로 m을 더하기
        else {    // 반시계 방향 회전
            for (int i = m; i >= 1; i--) {
                int next = i - k > 0 ? i - k : i - k + m;
                tmp[next] = arr[i];
            }
        }

        System.arraycopy(tmp, 1, arr, 1, arr.length - 1);
    }
    
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

 

2. 풀이 중점 사항

 

회전하기

 

가장 헷갈린 부분은 회전 처리하는 부분이었습니다.

시계 방향으로 회전을 하기 위해서는 이전 인덱스 i-1의 값이 i로 와야 하기 때문에 --> 이 방향으로 이동이 이뤄져야 합니다.

k 칸을 이동한다고 하는 것은 i번째의 값이 i + k에 도착해야 한다는 것을 의미합니다.

만약 i + k 가 m을 넘어가게 된다면 인덱스 에러가 발생합니다. 이를 해결하기 위해서는 

i + k > m ? i + k - m : i + k라는 수식을 구할 수 있습니다.

예를 들어 다음의 배열이 있습니다. (행과 열이 모두 1, 1부터 이므로 더미의 0번째 인덱스는 무시해야 합니다.)

 

0, 1, 2, 3, 4, 5

시계방향으로 3만큼 이동

=> 0, 4, 5, 1, 2, 3

3 인덱스는, 3 + 3으로 인해 인덱스가 6이 되어버립니다. 따라서, m만큼 개수를 빼면

6 - 5 = 1이 되어 정상적으로 위치 회전을 할 수 있습니다.

 

반시계 방향은 <-- 으로 이동해야 합니다.

수식은 i - k > 0? i - k : i - k + m;입니다.

 

0, 1, 2, 3, 4, 5 

반시계 방향으로 3만큼 이동

=> 0, 3, 4, 5, 1, 2 

1의 경우 3을 뺀다면, -2라서 에러가 발생하므로 5를 더해서 인덱스 3으로 만들 수 있습니다.

3 - 3의 경우 index가 0이지만, 0, 0은 더미로 설정하였으므로

5를 더하여 5로 설정할 수 있습니다. 4, 5는 인덱스가 0보다 크므로 i - k로 해결할 수 있습니다.

 

void swap(int[] arr, int k, int clockWise) { // k 만큼 스왑
    if(clockWise == 0) {    // 시계 방향 회전
        for (int i = 1; i <= m; i++) {
            int next = i + k > m ? i + k - m : i + k;
            tmp[next] = arr[i];
        }
    }

    // 반시계는 왼쪽으로 칸을 옮기되 0보다 작아질 수 있으므로 m을 더하기
    else {    // 반시계 방향 회전
        for (int i = m; i >= 1; i--) {
            int next = i - k > 0 ? i - k : i - k + m;
            tmp[next] = arr[i];
        }
    }

    System.arraycopy(tmp, 1, arr, 1, arr.length - 1);
}

 

점을 기준으로 특정 좌표를 회전시키거나 이렇게 swap 하는 유형은 실수하기 좋은 유형이므로 천천히 자세하게 적어가면서 해결해야 함을 느낄 수 있었습니다.

 

이성으로 원판 돌리기 자바 풀이를 마치겠습니다. 감사합니다.!!!