[Java/백준/배열] 16926번: 배열 돌리기 1, 17406번: 배열 돌리기 4

문제

www.acmicpc.net/problem/16926

16926번: 배열 돌리기 1

 

새로운 유형을 만나버렸다.

앞으로 많이 쓰일 것 같아서 고민하다 다른사람들의 풀이를 보고 방법을 아예 외워버렸다.

배열 전체를 반시계 방향으로 입력된 횟수만큼 돌려주면 된다.

 

여기서 고민할 것은 몇 겹의 layer로 이루어져 있는지,

어떻게 돌려줄 것인지 이다.

 

1. Layer 수

알아볼 수만 있음 되는 거지...?ㅠ

예를 들어 4 x 5 배열에선, 2번의 레이어를 돈다.

반 접히는 것을 생각해보면, Math.min(N, M)/2가 레이어의 수가 되는 것을 알 수 있다.

 

2. 반시계 방향으로 돈다.

각 레이어의 처음 원소를 보면, 첫번째 레이어에선 A[1][1],

두번째 레이어에선 A[2][2]이다.

이것을 tmp 변수에 미리 담아둔다.

 

그리는거 넘 어려워

첫번째 원소를 담아둔 뒤,

첫번째 원소를 반시계 방향이므로 덮는다. x 반복반복...

범위를 벗어날 때마다 edgeCnt를 증가시켜서 방향을 바꾸어준다.

 

(dy, dx의 방향을 잘못 설정했어서 여러번 애먹었다 ㅠㅠ)

 

edgeCnt==4가 되는 순간 과정을 마무리된다.

이 때 A[2][1]에는 처음 A[1][1]이 아닌 A[1][2]의 값이 들어가 있는 A[1][1]의 값이 대입되어 있다.

따라서 처음 A[1][1]의 값을 담은 tmp를 대입시켜준다.

 

 

package boj;

import java.io.*;

public class BOJ16926 {

	static int r, c, rotation, num;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] info = br.readLine().split("\\s");
		r = Integer.parseInt(info[0]);
		c = Integer.parseInt(info[1]);
		rotation = Integer.parseInt(info[2]);

		map = new int[r][c];

		for (int i = 0; i < r; i++) {
			String[] line = br.readLine().split("\\s");
			for (int j = 0; j < c; j++) {
				map[i][j] = Integer.parseInt(line[j]);
			}
		}

		num = Math.min(r, c) / 2; // 회전할 레이어 수
		for (int i = 0; i < rotation; i++) {
			rotateMap();
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				sb.append(map[i][j]+" ");
			}
			sb.append('\n');
		}
		System.out.println(sb);
		
		br.close();
	}

	private static void rotateMap() {
		for (int n = 0; n < num; n++) {
			int tmp = map[n][n];

			int edgeCnt = 0;
			int lx = n, ly = n;
			while (edgeCnt < 4) {
				// 한 칸 이동
				int ny = ly + dy[edgeCnt]; // 우하좌상
				int nx = lx + dx[edgeCnt]; // 우하좌상 의 숫자를 덮어씀

				// 다음 칸 좌표 확인
				if (ny >= n && nx >= n && ny < r - n && nx < c - n) {
					map[ly][lx] = map[ny][nx]; // 이전 점의 값을 다음 점의 값으로 치환
					ly = ny; // 현재 점을 다음 점의 값으로 바꾸고 while문을 다시 돌린다
					lx = nx;
				} else {
					edgeCnt++; // 다음 점이 범위를 벗어났으므로 꺾는다.
				}

			}
			
			map[n+1][n] = tmp;
		}
	}

}

 

 

 

 

 

문제

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

 

 

위 문제에 비해 더 나에게 가혹했던 문제...ㅠ

문제를 잘 읽어야 한다.

 

자꾸 틀려서 원인이 뭘까 했는데 연산을 수행한 순서에 따라 최종 배열이 달라진다. 그 중 최소값을 구하는 것이었다.

연산들을 모두 String[][] operations에 담아 두었다. 이후 순열을 이용해서 연산 순서를 정해주었다.

→ makePermutation 함수 참고

예를 들어, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우이다.

operations = {{3, 4, 2}, {4, 2, 1}}에는 담기게 된다. 

permArr의 결과로 {1, 0}이 나온다면 (4, 2, 1) 연산이 먼저, 그 뒤에 (3, 4, 2) 연산을 진행한다.

{0, 1}이면 그 반대 순서인 것이다. permArr의 각 요소의 값이 operations의 인덱스가 되는 것이다.

permArr이 완성되어 회전을 하고 난 뒤 다시 배열을 원상태로 돌려주는 것도 잊으면 안된다.

 

나머지는 배열돌리기 1에서 범위만 바꾸어 주었다.

 

 

package boj;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class BOJ17406 {

	static int row;
	static int col;
	static int rotation;
	static int[][] map;
	static int[][] originMap;
	static String[][] operations;
	static int min = Integer.MAX_VALUE;

	static int[] dy = { 1, 0, -1, 0 };
	static int[] dx = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] info = br.readLine().split("\\s");
		row = Integer.parseInt(info[0]);
		col = Integer.parseInt(info[1]);
		rotation = Integer.parseInt(info[2]);
		map = new int[row][col];
		originMap = new int[row][col];

		for (int i = 0; i < row; i++) {
			String[] line = br.readLine().split("\\s");
			for (int j = 0; j < col; j++) {
				map[i][j] = Integer.parseInt(line[j]);
				originMap[i][j] = map[i][j];
			}
		}

		operations = new String[rotation][3];
		for (int i = 0; i < rotation; i++) {
			String[] posInfo = br.readLine().split("\\s");
			operations[i] = new String[3];
			operations[i][0] = posInfo[0];
			operations[i][1] = posInfo[1];
			operations[i][2] = posInfo[2];
		}

		// permutation
		makePermutation(0, new int[operations.length], new boolean[operations.length]);
		System.out.println(min);
		br.close();
	}

	private static void makePermutation(int cnt, int[] permArr, boolean[] visited) {
		if (cnt == operations.length) {
			for (int i = 0; i < cnt; i++) {
				rotation(Integer.parseInt(operations[permArr[i]][0]) - 1,
						Integer.parseInt(operations[permArr[i]][1]) - 1, Integer.parseInt(operations[permArr[i]][2]));
			}
			calculateMin();
			recoverMap();
			return;
		}

		for (int i = 0; i < operations.length; i++) {
			if (!visited[i]) {
				visited[i] = true;
				permArr[cnt] = i;
				makePermutation(cnt + 1, permArr, visited);
				visited[i] = false;
			}
		}

	}

	private static void recoverMap() {
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				map[i][j] = originMap[i][j];
			}
		}
	}

	private static void calculateMin() {
		for (int i = 0; i < row; i++) {
			int sum = 0;
			for (int j = 0; j < col; j++) {
				sum += map[i][j];
			}
			min = Math.min(min, sum);
		}
	}

	private static void rotation(int r, int c, int num) {

		for (int i = 0; i < num; i++) {
			int tmp = map[r - num + i][c - num + i];

			int ly = r - num + i;
			int lx = c - num + i;
			int edgeCnt = 0;
			while (edgeCnt < 4) {
				int ny = ly + dy[edgeCnt];
				int nx = lx + dx[edgeCnt];

				if (ny >= r - num + i && nx >= c - num + i && ny <= r + num - i && nx <= c + num - i) {
					map[ly][lx] = map[ny][nx];
					ly = ny;
					lx = nx;
				} else {
					edgeCnt++;
				}
			}
			map[r - num + i][c - num + i + 1] = tmp;
		}

	}

}