백준 17406 - 배열 돌리기 4

문제

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

풀이

• 주어진 문제의 조건에서 회전의 순서가 달라지면 결괏값이 달라진다.
• 회전 순서의 경우의 수는 $K!$로 순열의 형태인데, $K=6$인 최악의 경우에도 720 남짓의 값으로 백트래킹을 통해 모든 경우의 수를 다 구하더라도 시간 제한 조건내에 풀이가 가능할 것으로 생각했다.
• 따라서 회전 연산의 정보를 저장한 뒤 모든 경우의 수를 dfs를 이용한 백트래킹으로 구하며 가장 작은 한 행의 모든 수의 합 값을 갱신하며 도출하는 방식으로 로직을 구성했다.
• 회전 연산을 구현할 때 경우별로 배열을 새로 할당하게 되면 공간 복잡도 조건을 초과하지 않을까 염려하였다. 하지만 $K=6$일 때 $K!=6!=720$이고 $N,M=50$인 최악의 경우에 각 경우별로 할당되는 2차원 배열의 크기는 $4\times50\times50=10000=10KB$이다. 따라서 총 할당되는 공간의 크기는 $720\times10KB=7200KB=7.2MB$로 제한 조건 $512MB$를 가뿐히 통과한다.
• 배열에 값을 할당하거나 순회하는 로직의 시간복잡도는 $O(NM)$이고 dfs의 시간복잡도는 $K!$이므로 $N,M=50\;,K=6$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

  static int N, M, K;
  static int[][] arr;
  static boolean[] visited;
  static int[] sequence;
  static List<RotationInfo> rotationInfos;
  static int minRowSum = MAX_VALUE;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = parseInt(st.nextToken());
    M = parseInt(st.nextToken());
    K = parseInt(st.nextToken());

    arr = new int[N][M];
    visited = new boolean[K];
    sequence = new int[K];
    for (int r = 0; r < N; r++) {
      st = new StringTokenizer(br.readLine());
      for (int c = 0; c < M; c++) {
        arr[r][c] = parseInt(st.nextToken());
      }
    }

    rotationInfos = new ArrayList<>();
    for (int i = 0; i < K; i++) {
      st = new StringTokenizer(br.readLine());
      int r = parseInt(st.nextToken()) - 1;
      int c = parseInt(st.nextToken()) - 1;
      int s = parseInt(st.nextToken());

      rotationInfos.add(new RotationInfo(r, c, s));
    }

    int[][] result = new int[N][M];
    deepCopy(arr, result);

    dfs(0);
    System.out.println(minRowSum);
    br.close();
  }

  static void deepCopy(int[][] arr, int[][] temp) {
    for (int r = 0; r < arr.length; r++) {
      for (int c = 0; c < arr[r].length; c++) {
        temp[r][c] = arr[r][c];
      }
    }
  }

  static int getMinRowSum(int[][] arr) {
    int value = MAX_VALUE;

    for (int r = 0; r < N; r++) {
      int sum = Arrays.stream(arr[r]).sum();
      value = Math.min(value, sum);
    }

    return value;
  }

  static int[][] rotate(int[][] arr, RotationInfo info) {
    int[][] temp = new int[N][M];
    deepCopy(arr, temp);

    for (int s = 1; s <= info.s; s++) {
      for (int c = info.c - s; c < info.c + s; c++) {
        temp[info.r - s][c + 1] = arr[info.r - s][c];
      }

      for (int r = info.r - s; r < info.r + s; r++) {
        temp[r + 1][info.c + s] = arr[r][info.c + s];
      }

      for (int c = info.c + s; c > info.c - s; c--) {
        temp[info.r + s][c - 1] = arr[info.r + s][c];
      }

      for (int r = info.r + s; r > info.r - s; r--) {
        temp[r - 1][info.c - s] = arr[r][info.c - s];
      }
    }

    return temp;
  }

  static void dfs(int depth) {
    if (depth == K) {
      int[][] result = new int[N][M];
      deepCopy(arr, result);
      for (int i = 0; i < sequence.length; i++) {
        result = rotate(result, rotationInfos.get(sequence[i]));
      }
      minRowSum = Math.min(minRowSum, getMinRowSum(result));
      return;
    }

    for (int i = 0; i < visited.length; i++) {
      if (visited[i]) {
        continue;
      }

      visited[i] = true;
      sequence[depth] = i;
      dfs(depth + 1);
      visited[i] = false;
    }
  }

  static class RotationInfo {

    int r, c, s;

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

결과