17406 - 배열 돌리기 4 [성공(반례힌트)|01:06:16]

boj.kr/17406

 

푼 과정

배열의 이동 연산이 K개 주어지면 그 K개를 모두 1번씩은 사용한 후 배열의 최솟값을 구하는 것이다.

 

배열의 회전 연산 K개를 어떤 순서로 하느냐에 따라 최종 배열의 모습이 달라지게 되므로 처음 생각해낸 아이디어는 '순열'이었다. 그래서 주어진 이동연산들을 2차원 배열에 담아 인덱스를 순열로 뽑는 알고리즘을 생각했다. 그렇게 K개가 뽑히게 된다면, 회전 연산을 수행하면 될 것 같았다.

 

회전 연산의 경우 이전에 풀었던 boj.kr/17144 문제에서 아이디어를 얻어 해당 구역들을 담으려고 했으나... 구역을 어떻게 담는지 생각하는 것보다 그냥 4번의 for문을 돌리는 것이 훨씬 빠르게 구현이 되는 것 같아서 4번의 for문으로 직접 회전 연산을 구현했다. 회전 연산을 수행할 때 첫 값만 tmp 변수에 담아두고 한 바퀴를 돌린 뒤에 마지막 위치에다가 tmp 값을 넣어주기만 하면 구현할 수 있다.

 

근데 생각해야 하는 것은 좌표가 점점 안쪽으로 들어간다는 점이다. 처음에 주어진 왼쪽 위 좌표와 오른쪽 아래 좌표의 변화를 보면 다음과 같다.

 

문제 속 예제 사진

• A[1][2] → A[2][3] → A[3][4]
• A[5][6] → A[4][5] → A[3][4]

 

이를 통해 알 수 있는건 왼쪽 위 좌표는 한 번의 회전 연산 후 x + 1, y + 1로 좌표가 변화하고 오른쪽 아래 좌표는 한 번의 회전 연산 후 x - 1, y - 1로 좌표가 변화한다. 그럼 둘의 좌표가 같아지거나 왼쪽 위 좌표가 오른쪽 아래 좌표보다 오른쪽에 오는 순간에 회전을 멈추면 된다.

 

이런 생각을 기반으로 다음과 같이 코드를 짰다.

 

 

코드

/**
 * 17406 - 배열 돌리기 4 [성공(반례힌트)|01:06:16]
 * 골드4, 구현/완전탐색, 시도3
 */

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

public class Main {
    // 시간제한 1초, 메모리제한 512MB
    // 크기 N*M인 배열 A
    // 배열 A의 값 == 각 행에 있는 모든 수의 합 중 최솟값
    // 1 2 3
    // 2 1 1
    // 4 5 6
    // 배열 A의 값 = 4
    // 회전 연산 가능 (r,c,s)
    // 가장 왼쪽 윗 칸 (r-s, c-s)
    // 가장 오른쪽 아래 칸 (r+s, c+s)
    // 배열 A와 회전 연산이 주어지면 회전 연산을 모두 한 번씩 사용해서 나오는 배열 A 값의 최솟값을 구하자.
    // 3 <= N, M <= 50

    // 왼쪽 위, 오른쪽 아래 좌표 대각선 안으로 이동 -> 둘의 좌표가 같아지면 회전 stop!!

    static int[][] A;
    static int[][] rcs;
    static int[] idxlist;
    static int N, M, K;
    static int ret = Integer.MAX_VALUE;

    static void swap(int idx1, int idx2) {
        int tmp = idxlist[idx1];
        idxlist[idx1] = idxlist[idx2];
        idxlist[idx2] = tmp;
    }

    static void permutation(int r) {
        if (r == K) {
            int[][] m = new int[N][M];
            for (int i = 0; i < N; i++)
                m[i] = A[i].clone();

            // 회전 연산 수행 후 최솟값 갱신
            for (int i = 0; i < K; i++) {
                int y1 = rcs[idxlist[i]][0] - rcs[idxlist[i]][2];
                int x1 = rcs[idxlist[i]][1] - rcs[idxlist[i]][2];

                int y2 = rcs[idxlist[i]][0] + rcs[idxlist[i]][2];
                int x2 = rcs[idxlist[i]][1] + rcs[idxlist[i]][2];

                while (y1 != y2 || x1 != x2) {
                    int tmp = m[y1][x1];

                    for (int y = y1 + 1; y <= y2; y++)
                        m[y-1][x1] = m[y][x1];
                    for (int x = x1 + 1; x <= x2; x++)
                        m[y2][x-1] = m[y2][x];
                    for (int y = y2 - 1; y >= y1; y--)
                        m[y+1][x2] = m[y][x2];
                    for (int x = x2 - 1; x > x1; x--) {
                        m[y1][x+1] = m[y1][x];
                        if (x == x1+1) m[y1][x] = tmp;
                    }

                    y1++;
                    x1++;
                    y2--;
                    x2--;
                }
            }

            for (int y = 0; y < N; y++) {
                int sum = 0;
                for (int x = 0; x < M; x++) {
                    sum += m[y][x];
                }

                ret = Math.min(sum, ret);
            }
            return;
        }

        for (int i = r; i < K; i++) {
            swap(i, r);
            permutation(r + 1);
            swap(i, r);
        }
    }

    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];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        rcs = new int[K][3];
        idxlist = new int[K];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            rcs[i][0] = Integer.parseInt(st.nextToken())-1;
            rcs[i][1] = Integer.parseInt(st.nextToken())-1;
            rcs[i][2] = Integer.parseInt(st.nextToken());
            idxlist[i] = i;
        }

        permutation(0);
        System.out.println(ret);
    }
}

 

순열에서 뽑힌 경우의 수마다 배열 A를 초기 입력값으로 초기화해주어야 하는데, 이 부분을 생각하지 못해서 이미 돌린 배열A에 대해 또 회전 연산을 수행했다. 그래서 오답이 나왔는데, 질문 게시판의 반례를 보고 이를 해결했다.

 

 

큰돌님 해설

배열 A 회전

(3, 4, 2) → (4, 2, 1)

(4, 2, 1) → (3, 4, 2)

배열을 돌리는 순서가 있다. == 순열

모든 순서를 체킹해야 하면서 값을 뽑아내는 단순 구현 문제

 

문제는 두 가지 파트로 나뉨

• 돌려야 할 영역 뽑아내기

원형으로 보지말고 1차원적으로 생각해보아라.

rbegin이 생각나야함. (교안 확인)

• 영역을 돌리는 연산 == rbegin

 

rbegin은 C++에서 사용할 수 있는 라이브러리 함수이므로 자바에서는 직접 구현해야한다.