[17406] 배열 돌리기4 in Java

 

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

17406번: 배열 돌리기 4

 

---

문제 요약

배열 크기 : N X M
1 ≤ r-s < r < r+s ≤ N
1 ≤ c-s < c < c+s ≤ M
가장 왼쪽 윗칸 (r-s,c-s), 가장 오른쪽 아랫 칸 (r+s,c+s)인 정사각형을 시계방향으로 한 칸씩 돌린다.

배열 A의 값 : 각 행의 모든 수의 합 중 최솟값
우리가 구해야하는 것 : 배열 A값 중에서 최솟값

---

 

 

문제 접근 방식

1. 순열을 통해 회전 연산의 순서를 정한다.

2. rotate 함수를 통해 회전 연산을 진행한다.

3. 회전연산을 모두 완료한 후 findMin() 함수를 통해 배열 A의 최솟값을 구한다.

4. tempArray에 원본 배열 array를 넣어 다시 초기화한다.

 

tempArray는 회전 작업 배열이고

array는 원본 배열이다.

 

회전 연산을 처음 진행할 때에는 원본배열로 시작해야 하기 때문에

원본 배열은 변경되면 안된다.

그래서 임시 배열 tempArray를 가지고

회전 연산을 진행해야 한다.

 

 

---

 

시행 착오

- rotate 함수 내에서 upX, upY, downX, downY의 값을 초기화해주는 과정이

잘못 되어있는 걸 뒤늦게 발견했다.

while문을 돌때마다 해당 변수에 +1씩 추가되도록 해야한다.

 

 

 

 

내가 전에 작성했던 코드는 아래와 같다.

틀린 코드

 

 

1번째에는 0이 더해진다.

2번째에는 1이 더해지고

따라서 k가 1이하일땐 문제가 일어나지 않는다

그래서 문제 사이트에서 주어진 테케가 올바르게 나왔나보다..

 

쨋든 k가 2 이상일때부터 오류가 발생하기 시작한다.

for문을 돌릴때마다 +1씩 증가하도록 설계를 해야하는데

위에 작성한 코드는 이에 해당하지 않는다.

 

(예시)

upX를 3이라고 가정한다.

 

k=0일때

upX = upX + 0 = upX

3 = 3+0 = 3

upX = 3

 

k=1일때

upX = upX + 1 = 3+1=4

upX=4

 

이제 여기서부터 문제가 발생한다.

k=2일때

upX = upX + 2 = 4 + 2 = 6

우리가 원하는 값은 upX + 1 = 4+1 = 5인데

6이라는 수가 나왔다...

 

따라서 이 코드는 틀린 코드였던 것이다!

 

 

따라서 이를 수정해주려면

 upX, upY . .. 의 변수 초기화를 for문 내에서 진행해주어야한다.

 

 

- (r,c,s)를 한꺼번에 저장하는 과정에서 어려움을 겪었다.

파이썬이었으면 튜플형식으로 묶어서 배열에 넣었을텐데

자바에서는 그게 되지 않았다..

 

그래서 고민한 결과

rotateArray라는 2차원 배열을 만들었다.

new int[K][3]

K행, 3열 크기의 배열을 만들었다.

rotateArray[0][0] = r 

rotateArray[0][1] = c

rotateArray[0][2] = s

 

 

package day_0810;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class study17406 {
    static int n; // 행
    static int m; // 열
    static int K; // 연산의 개수
    static int[][] array; // 원본 배열
    static int[][] tempArray; // 작업 배열
    static int[][] rotateArray; // r,c,s 보관 배열
    static boolean[] visited; // 방문 체크 배열
    static int[] selected; // 순열로 뽑은 순서 담아놓은 배열
    static int findMinAnswer=Integer.MAX_VALUE; // 배열값
 
    public static void findMin() {
        for(int i=1; i<=n; i++) {
            int temp=0;
            for(int j=1; j<=m; j++) {
                temp+=tempArray[i][j];
            }
            if (findMinAnswer>temp) {
                findMinAnswer=temp;
            }
        }
    }
    
    public static void permu(int cnt) {
        if (cnt==K) {
            for(int i=0; i<K; i++) {
                int curIdx=selected[i];
                int r=rotateArray[curIdx][0];
                int c=rotateArray[curIdx][1];
                int s=rotateArray[curIdx][2];
                rotate(r,c,s); // r,c,s 값 넘겨서 회전 진행
            }
            findMin(); // 배열 A의 최솟값 구하기
            // tempArray 초기화
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++) {
                    tempArray[i][j]=array[i][j];
                }
            }
            return;
        }
        for (int idx = 0; idx < K; idx++) {
            if (visited[idx]) {
                continue;
            }
            visited[idx]=true;
            selected[cnt]=idx;
            permu(cnt+1);
            visited[idx]=false;
            selected[cnt]=0;
        }
    }
    
    public static void rotate(int r,int c, int s) { 
        int[][] newArray = new int[n+1][m+1];
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                newArray[i][j]=tempArray[i][j];
            }
        }
        int upX; int upY; int downX; int downY;
        int depth=0;
        while(true) {
            upX=r-s+depth; // 가장 왼쪽 윗 칸 x값
            upY=c-s+depth; // 가장 왼쪽 윗 칸 y값
            downX=r+s-depth; // 가장 오른쪽 아랫 칸 x값
            downY=c+s-depth; // 가장 오른쪽 아랫 칸 y값
            
            if(upX>=downX || upY>=downY) break;
            
            // 시계방향
            // 1. 맨 윗줄 (오른쪽으로 1칸씩 이동)
            for(int i=upY; i<downY; i++) {
                newArray[upX][i+1]=tempArray[upX][i];
            }
            // 2. 맨 오른쪽 줄 (아랫쪽으로 1칸씩 이동)
            for(int i=upX; i<downX; i++) {
                newArray[i+1][downY]=tempArray[i][downY];
            }
            // 3. 맨 아랫 줄 (왼쪽으로 1칸씩 이동)
            for(int i=upY; i<downY; i++) {
                newArray[downX][i]=tempArray[downX][i+1];
            }
            // 4. 맨 왼쪽 줄 (윗쪽으로 1칸씩 이동)
            for(int i=upX; i<downX; i++) {
                newArray[i][upY]=tempArray[i+1][upY];
            }
            depth++;
        }
        // 변경된 배열 tempArray에 깊은 복사
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                tempArray[i][j]=newArray[i][j];
            }
        }
    }
    
    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()); // 회전 연산의 개수
        rotateArray=new int[K][3]; // r,c,s 담고 있는 2차원 배열
        selected=new int[K]; // 순열에서 사용하는 배열
        visited=new boolean[K]; // 순열에서 사용하는 배열
        
        // 배열 입력 받기
        array=new int[n+1][m+1]; 
        tempArray=new int[n+1][m+1]; 
        for(int i=1; i<=n; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 1; j <= m; j++) {
                array[i][j]=Integer.parseInt(st.nextToken());
                tempArray[i][j]=array[i][j];
            }
        }
        // 회전 연산
        for(int k=0; k<K; k++) {
            st=new StringTokenizer(br.readLine());
            int r=Integer.parseInt(st.nextToken()); // 행 
            int c=Integer.parseInt(st.nextToken()); // 열
            int s=Integer.parseInt(st.nextToken()); 
            // 회전 연산을 수행할 공간 범위 잡기 
            rotateArray[k][0]=r;
            rotateArray[k][1]=c;
            rotateArray[k][2]=s;
        }
        permu(0);
        
        // 최종값 출력하기
        System.out.print(findMinAnswer);
    }
}