boj 17406 배열 돌리기 4

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

앞의 배열 돌리기1, 2와 같이 배열이 주어지고 이 문제는 회전시킬 구간이 추가로 주어집니다.

구간은 r c s 이렇게 들어오는데 구간 (r - s, c - s) ~ (r + s, c + s)를 1번 회전시켜라는 뜻입니다.

하지만 이 연산 순서를 임의로 정해서 배열 A의 값을 최소로 해야하는 문제입니다.

즉, 구간정보를 브루트포스방식을 사용하여 모든 순서로 연산을 다 해봐야합니다.

 

연산 순서는 ArrayList를 활용하여 구간을 넣었다 뺐다 하는 방식으로 정하였고, 순서를 모두 정하면 list의 값을 복사한 다른 배열을 선언하여 모든 회전을 수행한 후에 A의 최솟값을 구하였습니다.

 

회전 로직은 1번, 2번과 같지만 구간에 해당하는 숫자가 1개인 경우 next로 자신으로 설정하는 예외처리를 해주었습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
    static ArrayList<int[]> rotate = new ArrayList<>();
    static ArrayList<int[]> rotatesolve = new ArrayList<>();
    static boolean visit[][], chk[];
    static int list[][], clist[][];
    static int N, M, K, r, c, s;
    static int sx, sy, ex, ey, ans = Integer.MAX_VALUE;
 
    static void print() {
        System.out.println(ans);
    }
 
    static int dfs(int x, int y, int idx) {
        visit[x][y] = true;
 
        int nx = x + direct[idx][0];
        int ny = y + direct[idx][1];
 
        if (nx < sx || ny < sy || nx > ex || ny > ey) {
            idx++;
            nx = x + direct[idx][0];
            ny = y + direct[idx][1];
            if (nx < sx || ny < sy || nx > ex || ny > ey) {
                nx = x;
                ny = y;
            }
        }
 
        if (visit[nx][ny]) {
            int tmp = clist[x][y];
            clist[x][y] = clist[nx][ny];
            return tmp;
        }
 
        int tmp = clist[x][y];
        clist[x][y] = dfs(nx, ny, idx);
        return tmp;
    }
 
    static void solve(int rr, int cc, int ss) {
        sx = rr - ss;
        sy = cc - ss;
        ex = rr + ss;
        ey = cc + ss;
 
        for (int i = 0;; i++) {
            dfs(sx, sy, 0);
            sx++;
            sy++;
            ex--;
            ey--;
            if (sx > ex || sy > ey)
                break;
        }
 
        for (int i = rr - ss; i <= rr + ss; i++) {
            Arrays.fill(visit[i], false);
        }
    }
 
    static void func(int cnt) {
        if (cnt == K) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++)
                    clist[i][j] = list[i][j];
            }
            for (int i = 0; i < K; i++) {
                solve(rotatesolve.get(i)[0], rotatesolve.get(i)[1], rotatesolve.get(i)[2]);
            }
 
            for (int i = 1; i <= N; i++) {
                int sum = 0;
                for (int j = 1; j <= M; j++) {
                    sum += clist[i][j];
                }
                ans = Math.min(ans, sum);
            }
 
            return;
        }
 
        for (int i = 0; i < K; i++) {
            if (chk[i])
                continue;
 
            rotatesolve.add(rotate.get(i));
            chk[i] = true;
            func(cnt + 1);
            chk[i] = false;
            rotatesolve.remove(cnt);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        list = new int[N + 1][M + 1];
        clist = new int[N + 1][M + 1];
        visit = new boolean[N + 1][M + 1];
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            rotate.add(new int[] { r, c, s });
        }
 
        chk = new boolean[K];
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0);
        print();
    }
}