[백준] 17406번 배열 돌리기 4 - Java

문제 링크

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

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

알고리즘: 구현, 브루트포스 알고리즘, 백트래킹

풀이

회전 연산은 모두 사용해야 하고, 순서에 따라 값이 달라지기 때문에 순열을 사용한다.
그리고 회전 연산을 적용해서 배열 A의 최솟값을 출력한다.

이 문제는 99% 구현 문제이기 때문에 회전 연산만 주의해서 풀면 쉽게 풀 수 있다.

나는 회전 연산을 적용할 때 left top과 right bottom을 기준으로 해서 적용했다.
예를 들면 맨 위에 부분은 left top과 y값은 같고 x는 +1씩 증가한다. 그리고 x값이 right bottom의 x와 같아지면 이제는 y가 +1씩 증가한다. 이런 식으로 회전 연산을 적용했다.

소스 코드

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

class RotationInfo {
    int r, c, s;
    RotationInfo(int r, int c, int s) {
        this.r = r;
        this.c = c;
        this.s = s;
    }
}

class Coordinate {
    int x, y;
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int N,M,K;
    static int A[][];
    static ArrayList<RotationInfo> rotation_list = new ArrayList<>();
    static Stack<RotationInfo> result = new Stack<>();
    static int ans = Integer.MAX_VALUE;
    static boolean visited[];
    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());
      K = Integer.parseInt(st.nextToken());
      A = new int[N][M];
      visited = new boolean[K];
      for(int i=0; i<N; i++) {
          StringTokenizer n_st = new StringTokenizer(br.readLine());
          for(int j=0; j<M; j++) {
              A[i][j] = Integer.parseInt(n_st.nextToken());
          }
      }
      for(int i=0; i<K; i++) {
          StringTokenizer n_st = new StringTokenizer(br.readLine());
          rotation_list.add(new RotationInfo(Integer.parseInt(n_st.nextToken()), Integer.parseInt(n_st.nextToken()), Integer.parseInt(n_st.nextToken())));
      }
      DFS();
      System.out.println(ans);
    }
    static void DFS() {
        if(result.size() == K) {
            int clone_A[][] = new int[N][M];
            deep_copy(clone_A);
            for(int i=0; i<result.size(); i++) {
                rotation_operation(result.get(i), clone_A);
            }
            for(int i=0; i<clone_A.length; i++) {
                int sum = 0;
                for(int j=0; j<clone_A[i].length; j++) {
                    sum += clone_A[i][j];
                }
                ans = Math.min(ans, sum);
            }
            return;
        }
        for(int i=0; i<K; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result.push(rotation_list.get(i));
                DFS();
                visited[i] = false;
                result.pop();
            }
        }
    }
    
    static void deep_copy(int arr[][]) {
        for(int i=0; i<arr.length; i++) {
            arr[i] = A[i].clone();
        }
    }
    
    static void rotation_operation(RotationInfo n, int n_A[][]) {
        int repeat = ((n.c + n.s) - (n.c - n.s) + 1)/2; //반복 횟수
        for(int i=0; i<repeat; i++) {
            Coordinate lt = new Coordinate(n.c - n.s - 1 + i, n.r - n.s - 1 + i); //left top
            Coordinate rb = new Coordinate(n.c + n.s - 1 - i, n.r + n.s - 1 - i); //right bottom
            //left top부터 시작
            Coordinate cur_cdn = new Coordinate(lt.x, lt.y);
            int cur_v = n_A[lt.y][lt.x];
            while(true) {
                if(cur_cdn.x == lt.x && cur_cdn.y == lt.y+1) {
                    n_A[lt.y][lt.x] = cur_v;
                    break;
                }
                int temp = 0;
                if(cur_cdn.x != rb.x && cur_cdn.y == lt.y) {
                    temp = n_A[cur_cdn.y][cur_cdn.x+1];
                    n_A[cur_cdn.y][cur_cdn.x+1] = cur_v;
                    cur_cdn = new Coordinate(cur_cdn.x+1, cur_cdn.y);
                } else if(cur_cdn.x == rb.x && cur_cdn.y != rb.y) {
                    temp = n_A[cur_cdn.y+1][cur_cdn.x];
                    n_A[cur_cdn.y+1][cur_cdn.x] = cur_v;
                    cur_cdn = new Coordinate(cur_cdn.x, cur_cdn.y+1);
                } else if(cur_cdn.x != lt.x && cur_cdn.y == rb.y) {
                    temp = n_A[cur_cdn.y][cur_cdn.x-1];
                    n_A[cur_cdn.y][cur_cdn.x-1] = cur_v;
                    cur_cdn = new Coordinate(cur_cdn.x-1, cur_cdn.y);
                } else if(cur_cdn.x == lt.x && cur_cdn.y != lt.y) {
                    temp = n_A[cur_cdn.y-1][cur_cdn.x];
                    n_A[cur_cdn.y-1][cur_cdn.x] = cur_v;
                    cur_cdn = new Coordinate(cur_cdn.x, cur_cdn.y-1);
                }
                cur_v = temp;
            }
        }
    }
}