[BOJ/Java] 17406. 배열 돌리기 4

[BOJ/Java] 17406. 배열 돌리기 4

 

17406번: 배열 돌리기 4

---

문제 해석

N x M 크기의 배열에서 특정 연산을 K번 수행할 수 있다. 연산은 배열의 부분을 회전시키는 것이며, 목표는 모든 연산을 수행한 후 배열의 각 행의 합 중 최소값을 찾는 것이다.

풀이 과정

• io 메소드는 입력을 받아 초기 배열 상태와 회전 연산을 저장한다.
• sol 메소드에서는 주어진 회전 연산의 모든 순열을 생성하고(permutation 메소드), 각 순열에 대해 배열을 회전시킨 후(slide 메소드), 결과 배열의 각 행의 합의 최소값을 계산한다(getResult 메소드).

코드

package edu.ssafy.im.BOJ.Gold.G4.No17406;

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

public class Main {
    private int n, m, k;
    private int[][] graph;
    private ArrayList<Operation> operationList;
    private int ans;

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() 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.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        operationList = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());
            operationList.add(new Operation(r, c, s));
        }
        
        ans = Integer.MAX_VALUE;
        sol(); // 문제 해결 메소드 호출
        
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
    }

    private void sol() {
        permutation(0, 0, new int[operationList.size()]);
    }

    // 회전 연산에 대한 모든 순열을 생성
    private void permutation(int k, int v, int[] sel) {
        if (k == sel.length) {
            slide(sel); // 선택된 순서로 배열 회전
            return;
        }

        for (int i = 0; i < sel.length; i++) {
            if ((v & (1 << i)) == 0) {
                sel[k] = i;
                permutation(k + 1, v | 1 << i, sel);
            }
        }
    }

    // 주어진 순서로 배열 회전 연산 수행
    private void slide(int[] sel) {
        int[][] copy = copy(); // 배열 복사
        for(int i : sel) {
            Operation o = operationList.get(i);
            for (int s = 1; s <= o.s; s++) {
                int r1 = o.r - s;
                int r2 = o.r + s;
                int c1 = o.c - s;
                int c2 = o.c + s;

                int upTmp = copy[r1][c2];
                for (int y = c2; y > c1; y--) {
                    copy[r1][y] = copy[r1][y-1];
                }
                
                int rightTmp = copy[r2][c2];
                for (int x = r2; x > r1; x--) {
                    copy[x][c2] = copy[x-1][c2];
                }
                copy[r1+1][c2] = upTmp;
                
                int leftTmp = copy[r2][c1];
                for (int y = c1; y < c2; y++) {
                    copy[r2][y] = copy[r2][y+1];
                }
                copy[r2][c2-1] = rightTmp;
                
                for (int x = r1; x < r2; x++) {
                    copy[x][c1] = copy[x+1][c1];
                }
                copy[r2-1][c1] = leftTmp;
            }
        }
        getResult(copy); // 회전 후 배열의 각 행의 합의 최소값 계산
    }

    // 배열 복사 메소드
    private int[][] copy() {
        int[][] copy = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copy[i][j] = graph[i][j];
            }
        }
        return copy;
    }

    // 배열의 각 행의 합의 최소값을 계산
    private void getResult(int[][] copy) {
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < m; j++) {
                sum += copy[i][j];
            }
            ans = Math.min(ans, sum);
        }
    }

    class Operation {
        int r, c, s;

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

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O((K!)×N×M×K)이다. 여기서 K는 회전 연산의 수, N과 M은 배열의 크기이다. 회전 연산의 모든 순열을 고려하고, 각 순열에 대해 배열을 회전시키며 각 행의 합을 계산한다.

느낀점

이 문제를 통해 배열과 순열을 다루는 복잡한 시뮬레이션 문제를 해결하는 방법을 배웠다. 효과적인 배열 조작과 순열 생성 기법이 중요하며, 이러한 기법은 다양한 문제 해결에 응용될 수 있다.