[ 백준 / 17406 ] 배열돌리기4 - java

문제 설명 

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3 2 1 1 4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6] ↑ ↓ A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6] ↑ ↑ ↓ ↓ A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6] ↑ ↑ ↓ ↓ A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6] ↑ ↓ A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6] A[6][1] A[6][2] A[6][3] A[6][4]   A[6][5] A[6][6]

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

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후
배열 A	(4, 2, 1) 연산 수행 후	(3, 4, 2) 연산 수행 후

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

 

분류 되어 있듯이 부르트포스 = 완전 탐색을 구현하는 알고리즘이다.

분명 맞게 풀었는데 여러번 틀리더니 이유는 단순히 원본 배열을 저장을 잘못해둔 문제였다ㅠㅠㅠ

배열 복사할 때에는 값을 각각 넣어주거나, copy함수를 써야 한다는 것을 기억하자!

먼저 해결한 자바 코드이다. 사용한 방법을 순열을 만들기 위해 next_permutation을 이용하였고, 그 다음 회전 연산을 수행하였다. 

 

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

public class 배열돌리기4 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int [][] A= new int[N][M];
		for(int i = 0; i<N;i++) {
			st =new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int min = Integer.MAX_VALUE;
		int[][]rcs = new int[K][3];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			rcs[i][0] = Integer.parseInt(st.nextToken());
			rcs[i][1] = Integer.parseInt(st.nextToken());
			rcs[i][2] = Integer.parseInt(st.nextToken());
		}
		// 순열 만들기 ( Next_permutation)
		int []np = new int[K];
		for (int i = 0; i < K; i++) {
			np[i] = i;
		}
		int [][]arr = new int[N][M];
		for(int i = 0;i<N;i++) {
			for(int j = 0; j<M;j++) {
				arr[i][j] = A[i][j];
			}
		}
		while(true) {
			//System.out.println(Arrays.toString(np));
			// 여기서 최대값 찾기 ( 회전 연산 ) 
			for (int n : np) {// 회전 순서
				//rcs[n]의 값 3,4,2,
				int r = rcs[n][0]-1,c=rcs[n][1]-1,s = rcs[n][2];
				while(s>0) {
					int a = A[r-s][c-s];
					for(int i = r-s; i+1<=r+s;i++) {
						A[i][c-s] = A[i+1][c-s];
					}
					for(int i = c-s;i+1<=c+s;i++) {
						A[r+s][i] = A[r+s][i+1];
					}
					for(int i = r+s;i-1>=r-s;i--) {
						A[i][c+s] = A[i-1][c+s];
					}
					for(int i = c+s; i-1>=c-s;i--) {
						A[r-s][i] = A[r-s][i-1];
					}
					A[r-s][c-s+1] = a;
					if(--s==0)break;
				}
				
			}
			for(int i = 0; i<N;i++) {
				int t = 0; 
				for (int j = 0; j < M; j++) {
					t+=A[i][j];
				}
				min = t<min?t:min;
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					A[i][j] = arr[i][j];
				}
			}
			int f = K-2;
			for (; f>=0  ; f--) {
				if(np[f]<np[f+1])break;
			}
			if(f==-1)break;
			int l = K-1;
			for(;l>f;l--) {
				if(np[f]<np[l])break;
			}
			int t = np[f];
			np[f]= np[l];
			np[l] = t;
			++f;
			for(int i = K-1;i>f;i--,f++) {
				t = np[i];
				np[i]= np[f];
				np[f] = t;
			}
		}
		System.out.println(min);
		
		
		
	}
}

 

자바에서 순열을 만들 수 있는 next_permutation을 사용하면 재귀 순열보다 빠르게 순열을 만들 수 있다. 

넥스트 퍼뮤테이션 원리 

Next Permutation 

위 방법으로 코딩하면 0,1,2,3 에서 3,2,1,0까지 순열을 생성할 수 있다. 

next_permutation 구현 코드 

순열에 따라 회전 하는 순서를 정하고, 이에 따라 회전하는데, 

회전 연산 구현 코드 

s는 얼마나 떨어진 값을 회전시키는지이고, 이 밑의 코드는 

회전을 하는 경우를 써놓았다. 값을 하나만 따로 int a에 A[1][2]의 값을 저장시켜두고, 

A[1][2]= A[2][2]로 덮어 쓰는 방식으로 역순으로 돌아가며 값을 넣어준다. 

마지막에  A[1][3]의 값에 이전에 A[1][2]=A[2][2]로 인해 들어간 A[2][2]값이 들어가게 되므로, A[1][3]값에 a를 넣어주면 

s=2일 경우의 회전이 끝난다. 

이후 s=1일 경우의 회전도 하면서 진행하게 된다. s==0일 경우 반복문을 빠져나간다. 

이후

최소값을 찾는 코드 

가장 작은 행의 합을 찾게 되고, 

이 것 떄문에 계속 틀려서 고생했다.. 반드시 잊지 말것 다 값을 넣어주어야 한다.

이후 원래의 값으로 돌려 놓으며 이후 코드가 진행될 수 있도록 한다. 

그리고 마지막으로min 값을 출력해 주면 결과가 출력된다.