BOJ17406_배열 돌리기4

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

문제정리

1. 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다.

1 2 3

2 1 1

4 5 6

인 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다

따라서 A의 값은 4이다.

2. 배열은 회전 연산을 수행할 수 있다.

(1) 회전 연산은 세 정수 (r,c,s)로 이루어져 있다

(2) 가장 왼쪽 윗 칸이 (r-s, c-s)이고 가장 오른쪽 아랫 칸이 (r+s,c+s)이다

(3) 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다.

(4) 크기가 6X6이고 회전 연산이 (3,4,2)인 경우 문제의 그림과 같이 회전한다.

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

4. 크기가 5X6이고 회전 연산이 (3,4,2) , (4,2,1)인 경우의 예시는 링크에 있다.

5. 배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A 값의 최솟값을 구해보자.

회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

문제issue

1. 회전하는 부분의 구현

2. map_clone까먹지 말자 , 변수 초기화 위치 생각하자

해결흐름

1. 회전 연산의 개수 k개에 대한 kPk개의 순열을 살펴본다.

2. 회전하는 부분 구현

(1) 순열 한개에서 왼쪽위의 위치와 오른쪽아래의 위치를 저장한다.

(2) 회전을 해야하는 구역의 중간 위치를 저장한다.(끝낼 조건을 위해)

(3) 왼쪽위부터 시작해서 움직일 변수 temp_r, temp_c를 왼쪽위 위치로 저장한다.

(4) 방향을 줄 변수를 선언한다.(0오른쪽, 1아래, 2왼쪽, 3위)

(5) 회전하는 방향대로 q에 넣어준다.

끝나는 조건은 중앙에 위치할 경우

각 꼭지점에 도착했을 때 방향을 틀어준다

처음위치로 오면 기준이 되는 왼쪽위 위치와 오른쪽 아래 위치를 변경해준다.

(6) q에 있는 숫자들을 map에 다시 넣어준다.

(7) map에 다시 넣어줄 때의 시작 위치는 왼쪽위에서 오른쪽으로 한칸 떨어진 위치에서

시작해야한다.

(8) q가 빌때까지 반복한다. map을 도는 방식은 위와 비슷하다.

3. 각 행의 합을 구하고 최솟값을 도출한뒤 전체에서의 최솟값을 도출한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static class info {
        int r;
        int c;
        int s;
 
        public info(int r, int c, int s) {
            super();
            this.r = r;
            this.c = c;
            this.s = s;
        }
    }
 
    private static int N;
    private static int M;
    private static int K;
    private static int[][] map;
    private static info[] arr;
    private static info[] temp_arr;
    private static boolean[] arr_visited;
    private static int result;
    private static int min;
    private static int[][] map_clone;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new int[N + 1][M + 1];
        map_clone = new int[N + 1][M + 1];
        arr = new info[K];
        temp_arr = new info[K];
        arr_visited = new boolean[K];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            arr[i] = new info(r, c, s);
        }
 
        // kPk순열 뽑기
        result = Integer.MAX_VALUE;
        min = Integer.MAX_VALUE;
        kPk(0);
        System.out.println(result);
 
    } // end of main
 
    private static void kPk(int len) {
        if (len == K) {
            // 배열돌리고 최솟값 구하는 곳 구현
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    map_clone[i][j] = map[i][j];
                }
            }
            solve();
            if (result > min)
                result = min;
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!arr_visited[i]) {
                arr_visited[i] = true;
                temp_arr[len] = arr[i];
                kPk(len + 1);
                arr_visited[i] = false;
            }
        }
    }
 
    private static int[] dr = { 0, 1, 0, -1 };
    private static int[] dc = { 1, 0, -1, 0 };
 
    private static void solve() {
        // temp_arr사용
        min = Integer.MAX_VALUE;
        for (int i = 0; i < temp_arr.length; i++) {
            Queue<Integer> q = new LinkedList<Integer>();
            int left_r = temp_arr[i].r - temp_arr[i].s;
            int left_c = temp_arr[i].c - temp_arr[i].s;
            int right_r = temp_arr[i].r + temp_arr[i].s;
            int right_c = temp_arr[i].c + temp_arr[i].s;
            int mid_r = (left_r + right_r) / 2;
            int mid_c = (left_c + right_c) / 2;
            int temp_r = left_r; // 게속 움직일 변수
            int temp_c = left_c;
            int dir = 0; // 0오른쪽 , 1아래, 2왼쪽, 3위
            // q.add먼저
            while (true) {
                if (left_r == mid_r && left_c == mid_c) {
                    q.add(map_clone[mid_r][mid_c]);
                    break;
                }
                q.add(map_clone[temp_r][temp_c]);
                temp_r += dr[dir];
                temp_c += dc[dir];
                // 방향전환
                if (temp_r == left_r && temp_c == right_c) {
                    dir = 1;
                } else if (temp_r == right_r && temp_c == right_c) {
                    dir = 2;
                } else if (temp_r == right_r && temp_c == left_c) {
                    dir = 3;
                }
                // 처음위치로 왔다
                if (temp_r == left_r && temp_c == left_c) {
                    left_r += 1;
                    left_c += 1;
                    right_r -= 1;
                    right_c -= 1;
                    temp_r = left_r;
                    temp_c = left_c;
                    dir = 0;
                }
            }
            // map에 다시 넣어주기
            left_r = temp_arr[i].r - temp_arr[i].s;
            left_c = temp_arr[i].c - temp_arr[i].s + 1;
            right_r = temp_arr[i].r + temp_arr[i].s;
            right_c = temp_arr[i].c + temp_arr[i].s;
            temp_r = left_r; // 게속 움직일 변수
            temp_c = left_c;
            dir = 0;
            while (!q.isEmpty()) {
                if (left_r == mid_r && left_c - 1 == mid_c) {
                    map_clone[mid_r][mid_c] = q.poll();
                    break;
                }
                map_clone[temp_r][temp_c] = q.poll();
                temp_r += dr[dir];
                temp_c += dc[dir];
                // 방향전환
                if (temp_r == left_r && temp_c == right_c) {
                    dir = 1;
                } else if (temp_r == right_r && temp_c == right_c) {
                    dir = 2;
                } else if (temp_r == right_r && temp_c == left_c - 1) {
                    dir = 3;
                }
                // 처음위치로 왔다
                if (temp_r == left_r && temp_c == left_c - 1) {
                    map_clone[temp_r][temp_c] = q.poll();
                    left_r += 1;
                    left_c += 1;
                    right_r -= 1;
                    right_c -= 1;
                    temp_r = left_r;
                    temp_c = left_c;
                    dir = 0;
                }
            }
        }
        int sum = 0;
        for (int j = 1; j <= N; j++) {
            sum = 0;
            for (int k = 1; k <= M; k++) {
                sum += map_clone[j][k];
            }
            if (min > sum)
                min = sum;
        }
    }
} // end of class