[백준] 18808번 : 스티커 붙이기 - 자바(JAVA)

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

18808번: 스티커 붙이기

 

문제 이해

여러 개의 스티커가 존재합니다.

스티커는 각 칸이 상하좌우로 모두 연결되어 있습니다.

주황색 칸은 스티커가 붙은 칸, 하얀색 칸은 스티커가 붙지 않은 칸을 나타냅니다.

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

모눈종이의 크기는 스티커의 크기와 꼭 맞아 스티커가 포함되지 않는 행이나 열은 존재하지 않습니다.

직사각형 모양의 노트북에 스티커들을 차례대로 붙이려고 합니다.

 

1. 스티커는 회전시키지 않고 모눈종이에서 떼어낸다.

2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다.

3. 만약 여러 곳에 스티커를 붙일 수 있다면 가장 위쪽, 위쪽이 겹친다면 가장 왼쪽 위치를 선택합니다.

4. 만약 스티커를 붙일 수 있는 위치가 전혀 없다면 스티커를 시계방향으로 90도 회전한 뒤 다시 2~3번을 반복합니다.

5. 스티커를 0도 90도 180도 270도 회전시켰음에도 스티커를 붙이지 못했다면 해당 스티커는 버려집니다.

 

문제 풀이 전 설계

우선 차례차례 스티커를 붙이기 때문에 배열 0,0부터 탐색을 하면서 스티커가 들어갈 자리를 찾습니다.

만약 붙일 수 있는 위치가 없다면 스티커를 시계방향으로 90도 돌려야 하기 때문에 배열을 90도 돌리는 함수를 만들어야 합니다.

만약 방향을 모두 돌렸음에도 스티커를 붙이지 못했다면 버려집니다.

 

핵심 로직1 - 배열 90도 회전시키기

static int[][] rotateArray(int[][] tempBoard) {
		// tempBoard [r][c]
		// copyBoard [c][r]
		int[][] copyBoard = new int[tempBoard[0].length][tempBoard.length];
		// rotate

		for (int y = 0; y < copyBoard.length; y++) {
			// 0~1
			for (int x = 0; x < copyBoard[0].length; x++) {
				// 0~3
				copyBoard[y][x] = tempBoard[copyBoard[0].length - 1 - x][y];
			}
		}
		tempBoard = copyBoard;
		return tempBoard;

	}

회전을 90도 시켜야 하므로 tempBoard가 r x c라면 copyBoard는 c x r 이여야 합니다.

tempBoard의 y좌표가 역순으로 copyBoard의 x좌표로 들어가야 하므로 y배열의 길이 - 1 - x를  사용하여 회전을 구현했습니다.

 

핵심 로직2 - 스티커 붙일 곳 탐색

private static boolean searchLocation(int[][] tempBoard) {
		int tempY = tempBoard.length;
		int tempX = tempBoard[0].length;
		
		int breakPointY = 0;
		int breakPointX = 0;
		boolean isSearched = false;
		
		
		breakPoint: for (int startY = 0; startY <= height - tempY; startY++) {
			continuePoint: for (int startX = 0; startX <= width - tempX; startX++) {
				for (int y = 0; y < tempBoard.length; y++) {
					for (int x = 0; x < tempBoard[0].length; x++) {
						// 만약에 한개라도 겹치면 붙일 수 없음.
						if (tempBoard[y][x] == 1 && noteBook[startY + y][startX + x] == 1) {							
							continue continuePoint;
						}
					}
				}
				// 여기 까지 왔다는 것은 스티커를 붙일 수 있다는 의미로 break
				breakPointY = startY;
				breakPointX = startX;
				isSearched = true;
				break breakPoint;
			}
		}
		
		if (!isSearched) {
			return isSearched;
		}

		// 이제 실제로 해당 위치에 스티커를 붙이기
		for (int y = 0; y < tempBoard.length; y++) {
			for (int x = 0; x < tempBoard[0].length; x++) {
				if (tempBoard[y][x] == 1) {
					noteBook[breakPointY + y][breakPointX + x] = 1;
					result++;
				}
			}
		}

		return isSearched;
	}

startY와 startX를 도입하여 출발점 기준으로 색종이를 쭉 붙여봅니다.

이때 tempBoard[y][x] ==1이라면 색종이를 붙어야 하는데 이미 노트북에 붙어있다면? ( noteBook [startY + y][startX + x] ==1)이라면 스티커를 붙일 수 없으므로 바로 다음칸으로 이동합니다.

 

모든 출발점 기준으로 검사해봐도 없다면 탐색을 하지 못한것이지 만약에 탐색에 성공한다면 바로 break 해서 스티커를 붙이고 종료합니다.

(항상 왼쪽위부터 순차적으로 검사하기 때문에 우선순위는 자동적으로  만족합니다.)

 

 

코드

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

public class Main_18808_스티커붙이기 {

	static int height, width, K, result;
	static List<int[][]> stickers = new ArrayList<int[][]>();
	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(), " ");
		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		noteBook = new int[height][width];

		// input data
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int[][] tempBoard = new int[r][c];
			for (int y = 0; y < r; y++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int x = 0; x < c; x++) {
					tempBoard[y][x] = Integer.parseInt(st.nextToken());
				}
			}
			stickers.add(tempBoard);
		}

		// main logic
		for (int[][] e : stickers) {
			int[][] tempBoard = e;
			boolean isFind = false;
			for (int i = 0; i < 4; i++) {
				// 0번째 0도 회전
				// 1번째 90도 회전
				// 2번째 180도 회전
				// 3번째 270도 회전

				// 현재 스티커배열로 들어갈 자리 탐색
				isFind = searchLocation(tempBoard);

				// 만약 적절한 자리에 들어가는 게 성공했다면 더 진행하지 않고 다음 스티커 진행
				if (isFind) {
					break;
				}
				tempBoard = rotateArray(tempBoard);				
			}
						
		}
		
		System.out.println(result);

	}

	private static boolean searchLocation(int[][] tempBoard) {
		int tempY = tempBoard.length;
		int tempX = tempBoard[0].length;
		
		int breakPointY = 0;
		int breakPointX = 0;
		boolean isSearched = false;
		
		
		breakPoint: for (int startY = 0; startY <= height - tempY; startY++) {
			continuePoint: for (int startX = 0; startX <= width - tempX; startX++) {
				for (int y = 0; y < tempBoard.length; y++) {
					for (int x = 0; x < tempBoard[0].length; x++) {
						// 만약에 한개라도 겹치면 붙일 수 없음.
						if (tempBoard[y][x] == 1 && noteBook[startY + y][startX + x] == 1) {							
							continue continuePoint;
						}
					}
				}
				// 여기 까지 왔다는 것은 스티커를 붙일 수 있다는 의미로 break
				breakPointY = startY;
				breakPointX = startX;
				isSearched = true;
				break breakPoint;
			}
		}
		
		if (!isSearched) {
			return isSearched;
		}

		// 이제 실제로 해당 위치에 스티커를 붙이기
		for (int y = 0; y < tempBoard.length; y++) {
			for (int x = 0; x < tempBoard[0].length; x++) {
				if (tempBoard[y][x] == 1) {
					noteBook[breakPointY + y][breakPointX + x] = 1;
					result++;
				}
			}
		}

		return isSearched;
	}

	static int[][] rotateArray(int[][] tempBoard) {
		// tempBoard [r][c]
		// copyBoard [c][r]
		int[][] copyBoard = new int[tempBoard[0].length][tempBoard.length];
		// rotate

		for (int y = 0; y < copyBoard.length; y++) {
			// 0~1
			for (int x = 0; x < copyBoard[0].length; x++) {
				// 0~3
				copyBoard[y][x] = tempBoard[copyBoard[0].length - 1 - x][y];
			}
		}
		tempBoard = copyBoard;
		return tempBoard;

	}

	static void printAllStickersTest() {
		for (int i = 0; i < K; i++) {
			int[][] tempBoard = stickers.get(i);
			printArrayTest(tempBoard);
		}
	}

	static void printArrayTest(int[][] tempBoard) {
		for (int y = 0; y < tempBoard.length; y++) {
			for (int x = 0; x < tempBoard[y].length; x++) {
				System.out.print(tempBoard[y][x] + " ");
			}
			System.out.println();
		}
	}

}