[백준] 18808번 : 스티커 붙이기

문제

 

접근 방식

문제의 포인트는 배열을 돌리는 것인데 직접 원소들을 움직일 수도 있지만

90도씩 회전할 때마다 배열의 요소들이 어떻게 움직이는지만 안다면

배열을 움직이지 않고도 풀 수 있다.

 

 

만약 위와 같은 n행 m열의 스티커 배열이 주어졌다고 가정했을 때

배열을 90도씩 회전시켜 보겠다.

 

 

우선 오른쪽으로 90도 회전시켰을 때를 살펴보면

행과 열이 뒤집히고 뒤집히기 전의 n행부터 1번째행까지의 첫 열의 값들이

첫 행에 위치하고 있고 그 아래줄부터는 다시 n행부터 1번째행까지의 두 번째 열의 값들이

위치하고 있는 것을 알 수 있다.

 

 

인덱스를 정리하면 위와 같다.

 

 

한 번 더 90도를 회전하면 위와 같고

다시 행과 열이 뒤집혀 원본 상태에서 인덱스만 뒤집히기 때문에

원본 배열을 거꾸로 읽어주면 된다.

 

 

인덱스는 위와 같다.

 

 

마지막으로 90도 회전시키면 위와 같이

다시 행과 열이 뒤집히고 처음 90도 회전시킨 상태의

반대로 배열을 읽어주면 된다.

 

 

인덱스는 위와 같다.

 

실제로 배열의 원소들을 움직일 수도 있지만 배열이 돌아갈 때마다

원소들이 어떻게 움직이는지를 알아둔다면 나중에 비슷한 문제를 풀 때

도움이 될 거 같기에 한 번 규칙을 찾아서 풀어봤다.

 

풀고 나서 비트 연산을 통한 풀이도 봤는데 아직 이런 방법으로는 풀이를 못 떠올리겠다...

 

시뮬레이션 문제들은 기능이나 중복된 코드들을 메서드로 분리하여

간결하고 가독성 있게 풀 수도 있지만 막상 풀고 나서 코드를 정리하려니 귀찮아서

풀 때부터 메서드로 분리하려고 노력해야겠다.

풀이

public class Main {

	private static int n;
	private static int m;
	private static int r;
	private static int c;
	private static int[][] sticker;
	private static int[][] notebook;

	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());
		int k = Integer.parseInt(st.nextToken());
		int result = 0;

		notebook = new int[n][m];

		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());

			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());

			sticker = new int[r][c];

			int plus = 0;

			for (int j = 0; j < r; j++) {
				st = new StringTokenizer(br.readLine());

				for (int l = 0; l < c; l++) {
					int num = Integer.parseInt(st.nextToken());
					sticker[j][l] = num;
					if (num == 1) plus++;
				}
			}

			if (stick()) result += plus;
		}

		System.out.println(result);
	}

	private static boolean stick() {
		for (int rota = 0; rota < 4; rota++) {
			if (rota % 2 == 0) {
				for (int i = 0; i <= n - r; i++) {
					for (int j = 0; j <= m - c; j++) {
						if (rotation(rota, i, j)) return true;
					}
				}
			} else {
				for (int i = 0; i <= n - c; i++) {
					for (int j = 0; j <= m - r; j++) {
						if (rotation(rota, i, j)) return true;
					}
				}
			}
		}
		return false;
	}

	private static boolean rotation(int rota, int st, int ed) {
		int a = 0;
		if (rota == 0) {
			for (int i = 0; i < r; i++) {
				int b = 0;
				for (int j = 0; j < c; j++) {
					if (sticker[i][j] == 1 && notebook[st + a][ed + b] == 1) return false;
					b++;
				}
				a++;
			}
			paste(rota, st, ed);
		} else if (rota == 1) {
			for (int i = 0; i < c; i++) {
				int b = 0;
				for (int j = r - 1; j >= 0; j--) {
					if (sticker[j][i] == 1 && notebook[st + a][ed + b] == 1) return false;
					b++;
				}
				a++;
			}
			paste(rota, st, ed);
		} else if (rota == 2) {
			for (int i = r - 1; i >= 0; i--) {
				int b = 0;
				for (int j = c - 1; j >= 0; j--) {
					if (sticker[i][j] == 1 && notebook[st + a][ed + b] == 1) return false;
					b++;
				}
				a++;
			}
			paste(rota, st, ed);
		} else {
			for (int i = c - 1; i >= 0; i--) {
				int b = 0;
				for (int j = 0; j < r; j++) {
					if (sticker[j][i] == 1 && notebook[st + a][ed + b] == 1) return false;
					b++;
				}
				a++;
			}
			paste(rota, st, ed);
		}

		return true;
	}

	private static void paste(int rota, int st, int ed) {
		if (rota == 0) {
			for (int i = 0; i < r; i++) {
				int b = 0;
				for (int j = 0; j < c; j++) {
					if (sticker[i][j] == 1) notebook[st][ed + b] = 1;
					b++;
				}
				st++;
			}
		} else if (rota == 1) {
			for (int i = 0; i < c; i++) {
				int b = 0;
				for (int j = r - 1; j >= 0; j--) {
					if (sticker[j][i] == 1) notebook[st][ed + b] = 1;
					b++;
				}
				st++;
			}
		} else if (rota == 2) {
			for (int i = r - 1; i >= 0; i--) {
				int b = 0;
				for (int j = c - 1; j >= 0; j--) {
					if (sticker[i][j] == 1) notebook[st][ed + b] = 1;
					b++;
				}
				st++;
			}
		} else {
			for (int i = c - 1; i >= 0; i--) {
				int b = 0;
				for (int j = 0; j < r; j++) {
					if (sticker[j][i] == 1) notebook[st][ed + b] = 1;
					b++;
				}
				st++;
			}
		}
	}
}