백준 : 18808 스티커 붙이기

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

18808번: 스티커 붙이기

 

시뮬레이션 + 완탐 문제

 

한번에 AC를 받지 못했는데 그이유는 문제를 잘읽지 못해서였다.

 

스티커를 회전시키는 것은 맨위 맨왼쪽부터 서치하면서 모든공간에 이방향으로 못할때만 회전시킬수있다.

 

즉..... 1,1 에서 정방향스티커가 안된다고 회전시키고 1,1를 탐색하는것이 아니라 1,2   1,3 ... N,M 까지 가보면서 안되면 

 

스티커 방향을 회전시키는 것이다.

 

스티커[R][C] 크기에 대해서 회전환 배열은 copy[C][R] 이 될것이다. 이때 90 도 방향으로 회전시키면

 

copy[i][j] = 스티커[R-1-j][i] 라는것을 알수있다.

 

주어진 조건대로 탐색하면 된다.

 

package ps;

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

public class B18808 {
	static int N, M, K;
	static int map[][];

	static class STICKER {
		int r;
		int c;
		int m[][];

		public STICKER(int r, int c) {
			super();
			this.r = r;
			this.c = c;
			this.m = new int[r][c];
		}

		public void rotate() {
			int[][] copy = new int[this.c][this.r];
			for (int i = 0; i < this.r; i++) {
				for (int j = 0; j < this.c; j++) {
					copy[j][this.r - 1 - i] = this.m[i][j];
				}
			}
			this.m = copy;

			// r c swap
			int tmp = r;
			this.r = this.c;
			this.c = tmp;
		}
	}

	static STICKER sticker[];

	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());
		K = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		sticker = new STICKER[K];

		// sticker 저장

		for (int k = 0; k < K; k++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			sticker[k] = new STICKER(r, c);
			for (int i = 0; i < r; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < c; j++) {
					sticker[k].m[i][j] = Integer.parseInt(st.nextToken());
				}
			}
		}

		// sticker 저장 끝

		for (int k = 0; k < K; k++) {
			// sticker들을 채운다
			boolean check = false;
			for (int d = 0; d < 4; d++) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {

						check = isPossible(i, j, k);
						if (check)
							break;

					}
					if (check)
						break;
				}
				if (check)
					break;
				sticker[k].rotate();
			}
		}

		// map에서 1의 개수를 센다
		int ans = getCnt();
		System.out.println(ans);

	}

	private static boolean isPossible(int y, int x, int k) {
		// 아래 범위 check
		if (y + sticker[k].r > N)
			return false;
		// 오른 쪽 범위 check
		if (x + sticker[k].c > M)
			return false;
		// 돌면서 1을 둘수있는지 없는지를 판단한다.
		for (int i = y, rr = 0; i < y + sticker[k].r; i++, rr++) {
			for (int j = x, cc = 0; j < x + sticker[k].c; j++, cc++) {
				if (map[i][j] == 1 && sticker[k].m[rr][cc] == 1)
					return false;
			}
		}

		// 이걸 다통과하면 map에다 심을 수 있다는것
		for (int i = y, rr = 0; i < y + sticker[k].r; i++, rr++) {
			for (int j = x, cc = 0; j < x + sticker[k].c; j++, cc++) {
				map[i][j] += sticker[k].m[rr][cc];
			}
		}

		return true;
	}

	private static int getCnt() {
		int cnt = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cnt += map[i][j];
			}
		}
		return cnt;
	}
}