BOJ - 스티커 붙이기

leehyunjon·2023년 1월 6일
0

Algorithm

목록 보기
153/162

18808 스티커 붙이기 : https://www.acmicpc.net/problem/18808


Problem


Solve

스티커를 노트북의 왼쪽 위부터 탐색하며 다른 스티커와 겹치지 않는 부분에 붙여주고 모두 확인하였을때 붙일곳이 없다면, 스티커를 90, 180, 270도로 회전시키며 붙일수 있는지 여부를 판단해주어야 합니다.

스티커를 회전했을때의 구현을 못하여서 다른 분의 풀이를 참조하였습니다.

먼저 구현하지 못했던 배열 회전부터 보겠습니다.

[4][3]크기의 A배열이 있습니다. A배열을 90도 회전한다면 [3][4]크기의 B배열이 되게 됩니다.

B[0][0] == A[3][0]이 되고, B[0][1] == A[2][0], B[0][2] == A[1][0], B[0][3] == A[0][0]으로 볼 수 있습니다.

이때 잘 보시면, B에서의 세로값이 A배열의 가로값과 대칭이 되는 것을 확인 할 수 있습니다.

또한 B배열의 가로값은 A배열의 세로값에서 1씩 감소하는 것을 확인 할 수 있습니다.

그렇다면 B[i][j] == A[R-1-j][i]으로 나타낼 수 있게 됩니다.

//스티커 회전
static void rotate() {
	int[][] tmp = new int[C][R];
	for (int c = 0; c < C; c++) {
		for (int r = 0; r < R; r++) {
			tmp[c][r] = sticker[R - 1 - r][c];
		}
	}

	sticker = tmp;

	int swap = R;
	R = C;
	C = swap;
}

스티커 회전에 대한 함수를 만들었으니, 이제 스터커를 노트북에 붙일수 있는지 확인해야합니다.
스티커가 주어졌을떄 순서대로 노트북에 붙일수 있는지 확인하고 만약 붙일 수 있다면 해당 스티커에 대한 탐색을 중지하고 다음 스티커를 확인해야합니다.
하지만 붙일 수 없다면 해당 스티커를 다시한번 회전하여 처음부터 노트북에 붙일수 있는지 확인해야합니다.

//break에 선언한 변수가 발생시 반복문을 한번에 중지시킬수 있는 java기능입니다.
out:
//총 3번 회전해야합니다.(3번째는 회전하지 않아도 무방합니다.)
for (int r = 0; r < 4; r++) {
	//해당 스티커의 크기에 맞는 곳까지만 탐색합니다.
    //i,j는 스티커를 붙일수 있는지 확인할 노트북의 시작 좌표입니다.
	for (int i = 0; i <= N - R; i++) {
		for (int j = 0; j <= M - C; j++) {
        	//시작 좌표부터 노트북에 있는 스티커와 스티커가 겹치는지 확인해야합니다.
			if (isAttachable(i, j))
				break out;
		}
	}
    //해당 모양의 스티커에서 노트북에 붙일 수 없다면 스티커를 회전시켜 다시 노트북의 끝부분부터 탐색해야합니다.
	rotate();
}
//현재 지점부터 스티커를 붙일수 있는지 확인하는 함수입니다.
static boolean isAttachable(int startR, int startC) {
	//노트북의 시작지점부터 스티커의 크기까지 비교합니다.
	for (int stickerR = 0; stickerR < R; stickerR++) {
		for (int stickerC = 0; stickerC < C; stickerC++) {
        	//노트북에 스티커가 붙어있고 붙이려는 스티커가 1로 겹친다면 해당 위치에 스티커를 붙일 수 없습니다.
			if (notebook[startR + stickerR][startC + stickerC] == 1 && sticker[stickerR][stickerC] == 1)
				return false;
		}
	}

	//반복문이 종료되었다면 해당 노트북 위치에 스티커를 붙일수 있습니다.
	attach(startR, startC);

	return true;
}

//스티커 붙이기
static void attach(int r, int c) {
	for (int sR = 0; sR < R; sR++) {
		for (int sC = 0; sC < C; sC++) {
			if (sticker[sR][sC] == 1)
				notebook[r + sR][c + sC] = 1;
		}
	}
}

Code

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

public class Main {
	static int[][] notebook;
	static int[][] sticker;
	static int N;
	static int M;
	static int R;
	static int C;

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		notebook = new int[N][M];

		while (K-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			sticker = new int[R][C];

			for (int i = 0; i < R; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < C; j++) {
					sticker[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			out:
			for (int r = 0; r < 4; r++) {
				for (int i = 0; i <= N - R; i++) {
					for (int j = 0; j <= M - C; j++) {
						if (isAttachable(i, j))
							break out;
					}
				}
				rotate();
			}
		}

		int answer = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (notebook[i][j] == 1)
					answer++;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static void rotate() {
		int[][] tmp = new int[C][R];
		for (int c = 0; c < C; c++) {
			for (int r = 0; r < R; r++) {
				tmp[c][r] = sticker[R - 1 - r][c];
			}
		}

		sticker = tmp;

		int swap = R;
		R = C;
		C = swap;
	}

	static boolean isAttachable(int startR, int startC) {
		for (int stickerR = 0; stickerR < R; stickerR++) {
			for (int stickerC = 0; stickerC < C; stickerC++) {
				if (notebook[startR + stickerR][startC + stickerC] == 1 && sticker[stickerR][stickerC] == 1)
					return false;
			}
		}

		attach(startR, startC);

		return true;
	}

	static void attach(int r, int c) {
		for (int sR = 0; sR < R; sR++) {
			for (int sC = 0; sC < C; sC++) {
				if (sticker[sR][sC] == 1)
					notebook[r + sR][c + sC] = 1;
			}
		}
	}
}

Result

배열 회전과 break문으로 반복문 중단 기능을 알게 되었습니다.


Reference

https://zzino.tistory.com/9

profile
내 꿈은 좋은 개발자

0개의 댓글