[백준/17406] 배열 돌리기 4(Java)

Question

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

• 분류 : Simulation

• 풀이 시간 : 50분

문제 해설

1. NxM 크기의 배열이 있을 때, 해당 배열의 값 = 각 행의 합 중 제일 작은 값
2. 배열 회전 연산
   1. 회전 연산 세 정수 (r, c, s)
   2. 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형 시계 방향으로 한칸식 회전
3. 회전 연산이 두 개 이상이면, 연산 수행 순서에 따라 최종 배열 다름
4. 사용 가능한 회전 연산을 이용해서 배열 값의 최솟값을 구하여라
5. 회전 연산을 모두 한번씩 사용 + 순서는 임의로 정해도 됨

Solution

풀이 접근 방법

1. 회전 연산을 모두 한번씩 사용 + 순서는 임의로 정해도 됨 = 회전 연산의 순열을 구해서 연산
   • 순열 = 순서들의 열거
2. 배열 회전 연산 방법
   • 가장 왼쪽 윗 좌표와, 가장 오른쪽 아랫 좌표만 알면 나머지 꼭짓점 좌표 다 알 수 있음
     

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
  static int N, M, K;
  static int[][] map, console;
  static int minRowSum;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.valueOf(st.nextToken());
    M = Integer.valueOf(st.nextToken());
    K = Integer.valueOf(st.nextToken());

    // 초기 배열 정보
    map = new int[N][M];
    // 연산을 담아둘 배열
    console = new int[K][3];
    minRowSum = Integer.MAX_VALUE;

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());

      for (int j = 0; j < M; j++) {
        map[i][j] = Integer.valueOf(st.nextToken());
      }
    }

    for (int k = 0; k < K; k++) {
      st = new StringTokenizer(br.readLine());

      int r = Integer.valueOf(st.nextToken()) - 1;
      int c = Integer.valueOf(st.nextToken()) - 1;
      int s = Integer.valueOf(st.nextToken());

      console[k] = new int[] { r, c, s };
    }

    // 연산의 순열 구함
    permutationConsole(new boolean[K], new LinkedList<Integer>());

    bw.write(minRowSum + "\n");
    bw.flush();
    bw.close();

  }

  static void permutationConsole(boolean[] visited, LinkedList<Integer> perm) {
    if (perm.size() == K) {
      // 원본 배열 복사하여 돌리기 수행
      int[][] nMap = copyMap();

      // 뽑힌 순열대로 배열 돌리기 수행
      for (Integer idx : perm) {
        int r = console[idx][0];
        int c = console[idx][1];
        int s = console[idx][2];

        calcPoint(r, c, s, nMap);
      }

      // 돌려진 배열로 배열 값 구하기
      minRowSum = Math.min(minRowSum, calcArr(nMap));
      return;
    }

    for (int i = 0; i < K; i++) {
      if (!visited[i]) {
        visited[i] = true;
        perm.add(i);

        permutationConsole(visited, perm);

        visited[i] = false;
        perm.removeLast();
      }
    }
  }

  static void calcPoint(int r, int c, int s, int[][] nMap) {
    for (int i = 0; i < s; i++) {
      // 가장 왼쪽 윗 칸 좌표
      int x1 = r - s + i;
      int y1 = c - s + i;
      // 가장 오른쪽 아랫 칸 좌표
      int x2 = r + s - i;
      int y2 = c + s - i;

      rotate(nMap, x1, y1, x2, y2);
    }
  }

  static void rotate(int[][] nMap, int x1, int y1, int x2, int y2) {
    int temp, pastTemp;

    // 진행 1 : 윗변
    temp = nMap[x1][y2];
    for (int y = y2; y > y1; y--) {
      nMap[x1][y] = nMap[x1][y - 1];
    }

    // 진행 2 : 오른쪽변
    pastTemp = temp;
    temp = nMap[x2][y2];

    for (int x = x2; x > x1; x--) {
      if (x - 1 == x1) {
        nMap[x][y2] = pastTemp;
        continue;
      }
      nMap[x][y2] = nMap[x - 1][y2];
    }

    // 진행 3 : 아랫변
    pastTemp = temp;
    temp = nMap[x2][y1];

    for (int y = y1; y < y2; y++) {
      if (y + 1 == y2) {
        nMap[x2][y] = pastTemp;
        continue;
      }

      nMap[x2][y] = nMap[x2][y + 1];
    }

    // 진행 4 : 왼쪽변
    pastTemp = temp;

    for (int x = x1; x < x2; x++) {
      if (x + 1 == x2) {
        nMap[x][y1] = pastTemp;
        continue;
      }

      nMap[x][y1] = nMap[x + 1][y1];
    }

    return;
  }

  static int calcArr(int[][] nMap) {
    int[] rowSum = new int[N];

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        rowSum[i] += nMap[i][j];
      }
    }

    Arrays.sort(rowSum);

    return rowSum[0];
  }

  static int[][] copyMap() {
    int[][] nMap = new int[N][M];

    for (int i = 0; i < N; i++) {
      System.arraycopy(map[i], 0, nMap[i], 0, M);
    }

    return nMap;
  }
}