[골드4] 17406. 배열 돌리기 4(Java)

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

17406번: 배열 돌리기 4

제발 배열 좀 내비둬여

---

※  문제를 요약하면 아래와 같습니다.

▶ 2차원 NxM 배열이 주어질 때, 각 행의 모든 수의 합 중 최소 값을 해당 배열의 최소값으로 지정

▶ 배열은 아래와 같은 회전 연산을 수행 가능

▶ (r,c,s) 가 주어졌을 경우 (r-s, c-s) ~ (r+s, c+s) 까지의 정사각형 배열 공간이 시계방향으로 회전

     ex) 5x6 배열 A의 회전 연산이 (3,4,2) => (4,2,1)의  예시

▶ 배열 A의 회전 연산 순서를 임의로 정할 수 있을 때,  최종 연산 후 의 배열 대표값이 가장 낮은 값 출력 

▶ Input : 첫째 줄에 배열 A의 크기 N,M 과 회전 연산의 개수 K, 이후 N개의 줄에 배열값, K개의 줄에 연산값 입력

▶ Output : 배열 A의 최종연산 값들 중 최소값 출력

---

◈ Input - 1

5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1

◈ Output - 1

12

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 0~K-1까지 중복되지 않도록 모든 가능한 연산 순서를 배치하여 저장  ( 백준 N과M (1)과 로직 동일)

▶ ArrayList의 제네릭을 int형 1차원 배열로 받아서 2차원 자료구조 형태로 배치 가능한 모든 경우의 수 저장

▶ 배열은 시계방향으로 회전 -> 동,남,서,북 으로 회전하는 델타 탐색 구현

▶ 회전 연산의 배열 공간은 반드시 정사각형으로 주어지며 길이는 (s * 2) 아래와 같은 규칙이 존재

    1. 시계 방향으로 한 번 탐색을 완료하면 길이는 2가 줄어듬

    2. 다음 시계 방향 출발점은 이전 시작점의 row+1, col+1

    3. 정사각형의 길이가 1이하가 될 때 까지 반복

▶ 저장한 모든 연산 순서를, 하나씩 최종 연산까지 진행 후 최소값과 비교, 

        ( K-1번 까지 연산을 끝낸 후에 최소값을 비교!!!!!!)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, M, K, nMin;
	static int[][] narrData;
	static int[][] narrRotate;

	static int[][] narrCal;

	static int[] narrNums;
	static ArrayList<int[]> listOrders;

	static boolean[] barrNums;

	// 동, 서, 남, 북
	static int[] dr = { 0, 1, 0, -1 };
	static int[] dc = { 1, 0, -1, 0 };

	static boolean[][] barrVisit;

	public static void main(String[] args) throws IOException {
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		N = Integer.parseInt(st.nextToken()); // Row
		M = Integer.parseInt(st.nextToken()); // Col
		K = Integer.parseInt(st.nextToken()); // Cal

		narrData = new int[N][M];
		narrRotate = new int[N][M];

		narrCal = new int[K][3];

		narrNums = new int[K];
		barrNums = new boolean[K];
		listOrders = new ArrayList<>();

		// 배열 입력 받자
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < M; j++) {
				narrData[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 연산 입력 받자
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < 3; j++) {
				narrCal[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		nMin = Integer.MAX_VALUE;

		// 배열 연산의 순서 경우의 수를 전부 탐색하기 위해
		// 연산 가능한 순서를 전부 갖고오자아
		GetOrders(0);

		// 가능한 경우를 전부 테스트하여 최소값을 뽑아내자
		for (int i = 0; i < listOrders.size(); i++) {
			// 원본 배열로 다시 돌려줍시다
			for (int j = 0; j < N; j++) {
				for (int a = 0; a < M; a++) {
					narrRotate[j][a] = narrData[j][a];
				}
			}

			for (int j = 0; j < K; j++) {
				// 순서는 가능한 모든 경우의 수로 탐색
				int S = narrCal[listOrders.get(i)[j]][2];
				int nRow = narrCal[listOrders.get(i)[j]][0] - 1;
				int nCol = narrCal[listOrders.get(i)[j]][1] - 1;

				int nStartRow = nRow - S;
				int nStartCol = nCol - S;
				int nEndRow = nRow + S;
				int nEndCol = nCol + S;
				//System.out.println(j);
				
				RotateArray(nStartRow, nStartCol, nEndRow, nEndCol);
			}
			
			// 연산을 다 진행한 후에 최소값을 비교합니다 ^^
			for (int a = 0; a < N; a++) {
				int nSum = 0;
				for (int j = 0; j < M; j++) {
					nSum += narrRotate[a][j];
				}
				if (nMin > nSum)
					nMin = nSum;
			}
		}

		bWriter.write(String.valueOf(nMin));
		bWriter.close();

	}

	// 가능한 모든 경우의 수를 찾자
	private static void GetOrders(int nIndex) {
		// 기저 조건
		// K만큼 수를 저장했따
		if (nIndex == K) {
			int[] narrTemp = new int[K];

			// 늘 그랬듯 깊은 복사로 진행합니다아
			for (int i = 0; i < K; i++)
				narrTemp[i] = narrNums[i];
			listOrders.add(narrTemp);
		}

		// 재귀 조건
		// 0~K-1까지 값을 순서대로 저장
		for (int i = 0; i < K; i++) {
			if (!barrNums[i]) {
				barrNums[i] = true;
				narrNums[nIndex] = i;
				GetOrders(nIndex + 1);
				barrNums[i] = false;
			}
		}

	}

	// 배열을 회전시키자
	private static void RotateArray(int nStartRow, int nStartCol, int nEndRow, int nEndCol) {
		// TODO Auto-generated method stub
		int nLength = nEndCol - nStartCol;

		int nSearchRow = nStartRow;
		int nSearchCol = nStartCol;
		
		// 2차원 배열 깊은 복사
		int[][] narrCopy = new int[N][M];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++)
				narrCopy[i][j] = narrRotate[i][j];
		}
		
		// 회전 시켜버리자
		int nIndex = 0;
		while (nLength >= 2) {
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < nLength; j++) {
					// 회전 값 넣어주고
					narrCopy[nSearchRow + dr[nIndex]][nSearchCol + dc[nIndex]] = narrRotate[nSearchRow][nSearchCol];
					// System.out.println(nSearchRow + " / before");

					nSearchRow += dr[nIndex];
					nSearchCol += dc[nIndex];
				}
				nIndex++;
				if (nIndex >= 4)
					nIndex = 0;
			}
			nLength -= 2;
			nSearchRow += 1;
			nSearchCol += 1;
		}
		
		// 2차원 배열 깊은 복사
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++)
				narrRotate[i][j] = narrCopy[i][j];
		}

	}

}

---

Good Luck! (피드백 감사합니다!)