[백준 18808] 스티커 붙이기(JAVA)

링크

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

문제 설명

문제 규칙

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

문제 풀이

주어진 규칙에 맞게 짜면 해결.

주의할 점

• 가장 많이 붙일 수 있는 경우의 수가 아닌 처음 붙일 수 있는 경우를 구하는 문제이다.
• 따라서 주어진 스티커의 순서대로 왼쪽 상단부터 확인해가며 붙일 수 있다면 무조건 붙여야한다.

회고

• 문제를 제대로 읽지 않아서 빈칸의 수를 최소화 하며 풀어서 시간이 더 오래 걸렸었다.
  • 앞으로 문제를 더더 제대로 읽자!
• rotate 함수 부분에서도 틀렸었고, 더 좋은 코드를 찾아서 참고했다.
  • 다음 비슷한 문제에 이번에 작성한 rotate함수를 참고해보자!

소스코드

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

public class Baek_18808_스티커_붙이기 {
	static int N, M, K, ans = 0;
	static int[][] map;

	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];

		for (int k = 0; k < K; k++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int[][] 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());
				}
			}
			findLocation(sticker);
		}
		
		System.out.println(ans);
	}

	static void findLocation(int[][] sticker) {
		int r = sticker.length;
		int c = sticker[0].length;
		
		for (int d = 0; d < 4; d++) {
			if(d != 0)
				sticker = rotate(sticker, r, c);
			r = sticker.length;
			c = sticker[0].length;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (i + r > N || j + c > M)
						break;

					if (putOn(i, j, r, c, sticker)) {
						return;
					}
				}
			}
		}
	}

	static boolean putOn(int x, int y, int r, int c, int[][] sticker) {
		for (int i = x; i < x + r; i++) {
			for (int j = y; j < y + c; j++) {
				if (map[i][j] == 1 && sticker[i - x][j - y] == 1)
					return false;
			}
		}

		for (int i = x; i < x + r; i++) {
			for (int j = y; j < y + c; j++) {
				if(sticker[i-x][j-y] == 1) {
					map[i][j] = 1;
					ans++;
				}
			}
		}

		return true;
	}

	static int[][] rotate(int[][] sticker, int r, int c) {
		int[][] newSticker = new int[c][r];

		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++)
				newSticker[j][r - i - 1] = sticker[i][j];

		return newSticker;
	}
}

GITHUB

https://github.com/hoonze/SSAFY_Algorithm_Study/tree/master/SSAFYT_Study/etc/2022.01/Baek_18808_%EC%8A%A4%ED%8B%B0%EC%BB%A4_%EB%B6%99%EC%9D%B4%EA%B8%B0