[BJ 17406] 배열 돌리기4

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

17406번: 배열 돌리기 4

---

[1회차] 8월 11일 강의 시간

이 문제 너무 기억이 남. 수업 시간에 처음 풀었는데 그냥 무지성으로 배열 돌렸다가 매우X1000 헤깔려서 결국은 사망해버렸다는 전설이 깃든 문제였음. 배열 대신 내가 돌아감.

 

문제 로직 따위는 없이 문제 조건에 따라 전부 for 문으로 옮겨버렸다. 

 

그 때 어거지로 풀었던 코드를 공개합니다 뚜둔

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M, R;
    static int[][] originArr, cmds;
    static boolean[] visited;
    static int[] p;
    static int  minValue = Integer.MAX_VALUE;

public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

	    N = Integer.parseInt(st.nextToken());
	    M = Integer.parseInt(st.nextToken());
	    R = Integer.parseInt(st.nextToken());
	    
	    originArr = new int[N][M];
	    cmds = new int[R][3];
	    
	    visited = new boolean[R+1];
	    p = new int[R];
	    
	    for (int i = 0; i < N; i++) {
	        st = new StringTokenizer(in.readLine());
	        for (int j = 0; j < M; j++) {
	        	originArr[i][j] = Integer.parseInt(st.nextToken());
	        }
	    }
	    
	    for (int i = 0; i < R; i++) {
	        st = new StringTokenizer(in.readLine());
	        
	        cmds[i][0] = Integer.parseInt(st.nextToken());
	        cmds[i][1] = Integer.parseInt(st.nextToken());
	        cmds[i][2] = Integer.parseInt(st.nextToken());
	    }
	    
	    permutation(0);
	    System.out.println(minValue);
	}

	private static void permutation(int depth) {
	    if(depth == R) {
	    	int[][] copyArr = new int[N][M];
	    	for(int i = 0; i < originArr.length; i++){
                copyArr[i] = originArr[i].clone();                
            }
	        for(int item: p) {
	            copyArr = rotation(copyArr, cmds[item][0], cmds[item][1], cmds[item][2]);
	        }
	        sum(copyArr);
	        return;
	    }
	    
	    for (int i = 0; i < R; i++) {
	        if(!visited[i]) {
	            visited[i] = true;
	            p[depth] = i;
	            permutation(depth+1);
	            visited[i] = false;
	        }
	    }
	    
	}

    private static void sum(int[][] arr) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = 0; j < arr[i].length; j++) {
                sum += arr[i][j];
            }
            if(min > sum) {
                min = sum;
            }
        }
        if(min < minValue) {
            minValue = min;
        }
    }

    private static int[][] rotation(int[][] arr, int r, int c, int s) {
        // (r-s, c-s) 부터 (r+s, c+s) 까지의 값을 시계방향 회전 
        int rEnd = r+s-1; // 세로
        int cEnd = c+s-1; // 가로

        int cnt = 0;
        int xi = r-s-1;
        int xj = c-s-1;
        
        while(cnt != s) {
            Queue<Integer> ori = new LinkedList<>();
            int temp = arr[xi][xj];
           
            for(int i = xi+1; i <= rEnd; i++) {
                ori.add(arr[i][xj]);
            }
            for (int i = xi+1; i <= rEnd; i++) {
            		arr[i-1][xj] = ori.poll();
                
            }
            for(int i = xj+1; i <= cEnd; i++) {
                ori.add(arr[rEnd][i]);
            }
            for(int i = xj+1; i <= cEnd; i++) {
                arr[rEnd][i-1] = ori.poll();
            }
            for(int i = rEnd; i > xi; i--) {
                ori.add(arr[i-1][cEnd]);
            }
            for(int i = rEnd-1; i >= xi; i--) {
            	arr[i+1][cEnd] = ori.poll();
            }
            for(int i = cEnd; i > xj+1; i--) {
                ori.add(arr[xi][i-1]);
            }
            for(int i = cEnd-1; i > xj; i--) {
                arr[xi][i+1] = ori.poll();
            }
            arr[xi][xj+1] = temp;
            cnt++;
            xi++;
            xj++;
            cEnd--;
            rEnd--;
        }
        
        return arr;
    }
}

 

다만 큐로 풀었는데 아마 큐로 안 풀고 그냥 배열 하나 새로 만들어서 실행시켰다가 시간초과(?)가 났었던 것 같다. 그래서 큐를 이용해서 풀었는데 어떻게 저렇게 풀었지 싶음;;

 

시간 & 메모리

---

[2회차] 10월 27일 A형 대비

문제 접근 방법 (사용 자료구조, 알고리즘)

1. 입력 : N, M, K, 전체 배열 A[N][M], 회전 정보 배열 R[K][3]
2. R  배열의 요소의 수(K)만큼 회전을 진행해야 한다. 단, 회전을 수행하는 순서에 따라 결과가 다르므로 순서를 조합해준다.
3. 조합이 완료되면 조합된 순서에 따라 회전을 진행해준다.
4. [회전 1] 회전은 회전할 정사각형의 가로 (또는 세로) 의 길이 / 2 만큼 진행한다 -> 실제로 계산해봄
시작하는 변수의 값을 spare에 저장해 주면 배열의 한 칸이 빈다. 한 칸이 비면 나머지 요소들을 자유롭게 옮길 수 있으므로 한 칸을 애초에 빼 놓은 것이다. 
5. [회전 2] while문을 돌면서 방향 배열 값을 더해주며 회전 배열 범위 안에 있는 값들을 넣어준다.
6. [회전 3] 각각의 회전이 끝나면 시작점을 옮겨준다.
7. 배열의 최솟값을 계산한다. 

대충 이렇게 짰다는...

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 접근	코드 구현
5분	20분	40분

 

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, M, K, A[][], R[][], orders[], ans;
	static boolean visited[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		// 1. 입력 : origin 배열정보, 회전 정보 
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		A = new int[N][M];
		R = new int[K][3];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(in.readLine());
			R[i][0] = Integer.parseInt(st.nextToken());
			R[i][1] = Integer.parseInt(st.nextToken());
			R[i][2] = Integer.parseInt(st.nextToken());
		}
		
		// 2. 회전 - R 배열의 요소만큼 회전인데 연산을 수행하는 방법에 따라 다름 -> 조합
		visited = new boolean[K];
		orders = new int[K];
		ans = Integer.MAX_VALUE;
		combi(0);
		
		System.out.println(ans);
	}
	
	private static void combi(int depth) {
		if(depth == K) {
			int[][] B = new int[N][M];
			for (int i = 0; i < N; i++) {
				B[i] = A[i].clone();
			}
			
			// B 배열을 회전 순서대로 회전해주기 
			for (int i = 0; i < K; i++) {
				int[] cur = R[orders[i]];
				B = rotate(B, cur);
			}
			
			// 회전이 끝나면 배열 A의 최솟값 갱신해주기
			for (int i = 0; i < N; i++) {
				int sum = 0;
				for (int j = 0; j < M; j++) {
					sum += B[i][j];
				}
				ans = Math.min(ans, sum);
			}
			
			return;
		}
		
		for (int i = 0; i < K; i++) {
			if(!visited[i]) {
				visited[i] = true;
				orders[depth] = i;
				combi(depth+1);
				visited[i] = false;
			}
		}
	}

	private static int[][] rotate(int[][] B, int[] cur) {
		int dir[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
		// r, c, s = cur[]
		int r = cur[0];
		int c = cur[1];
		int s = cur[2];
		
		// spare로 남겨둘 변수 지정 
		int startR = r - s - 1;
		int startC = c - s - 1;
		
		// 회전 횟수 
		int cnt = (2 * s + 1) / 2;
		int curCnt = 0;
		
		while(curCnt < cnt) {
			int idx = 0;
			int spare = B[startR][startC];
			
			while(idx < 4) {
				int dr = startR + dir[idx][0];
				int dc = startC + dir[idx][1];
				
				// 다음 숫자를 현재 자리에 넣어줘야 한다. 조건에 맞을 경우 
				if(isBound(dr, dc, r, c, s - curCnt)) {
					B[startR][startC] = B[dr][dc];
					startR = dr;
					startC = dc;
				} else {
					idx++;
				}
				
			}
			
			B[startR][startC + 1] = spare;
			curCnt++;
			
			startR = r - s - 1 + curCnt;
			startC = c - s - 1 + curCnt;
		}
		
		return B;
	}

	private static boolean isBound(int dr, int dc, int r, int c, int s) {
		if(dr >= r - s - 1 && dr <= r + s - 1 && dc >= c - s - 1 && dc <= c + s - 1) return true;
		return false;
	}
}

 

 

메모리 & 시간

확실히 인덱스로만 장난(?)치니까 시간과 메모리가 줄었다.

 

 

 

느낀점

진짜 2달 전만 해도 어떻게 해야할지 감도 안 잡혔었는데 조그만 시간 사이 어 리를빗 성장했다. 사고력 1cm 성장.