[BOJ 18808] 스티커 붙이기 (Java)

BOJ 18808 스티커 붙이기

문제풀이

잠시 알고리즘 안풀었다고 이렇게 오래걸릴줄이야... 반성해야겠다.

이 문제는 단순 구현으로 문제에서 시키는대로 하면된다.

1. 현재 스티커를 붙일 수 있는지 확인한다.
   1-1. 붙일 수 있다면 붙이고 다음 스티커로 넘어간다.
   1-2. 붙일 수 없다면 시계방향으로 90도 회전하여 다시 확인한다.
2. 모든 스티커에 대해서 차례대로 위의 순서를 진행한다.
3. 스티커가 붙은 칸의 갯수를 세어본다.

이 문제의 핵심은

• 2차원 배열 돌리기 (배열 돌리기 알고리즘을 가장 쉽게 설명한 곳) 직사각형은 행, 열의 크기를 반대로한 배열을 생성하고 똑같이 하면 된다.
• 스티커를 붙일 수 있는지 확인할 때는 기존의 맵에 하면 안되고 복사한 맵에서 수행하고 붙일 수 있을 때 다시 원본 맵으로 복사해야한다.

구현코드

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

public class Main {
	
	static int[][] map;
	static int N, M, S, ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		S = stoi(st.nextToken());
		
		ans = 0;
		map = new int[N][M];
		
		// 스티커 갯수만큼 수행 
		for(int s = 0 ; s < S ; ++s) {
			// 스티커 입력 받기 
			st = new StringTokenizer(br.readLine());
			int R = stoi(st.nextToken());
			int C = stoi(st.nextToken());
			int[][] sticker = new int[R][C];
			
			for(int r = 0 ; r < R ; ++r) {
				st = new StringTokenizer(br.readLine());
				for(int c = 0 ; c < C ; ++c) {
					sticker[r][c] = stoi(st.nextToken());
				}
			}
			
			// 회전하기
			OUTER: for(int d = 0 ; d < 4 ; ++d) {
				sticker = rotate(d, sticker);
				
				// 시작지점 찾기 
				for(int r = 0 ; r < N ; ++r) {
					for(int c = 0 ; c < M ; ++c) {
						// 현재 지점에 스티커가 있거나 붙일 스티커가 노트북을 벗어날 경우
						if(r + sticker.length > N || c + sticker[0].length > M) continue;
						
						int[][] temp = copy(map);
						
						if(attach(temp, r, c, sticker)) {
							map = temp;
							break OUTER;
						}
					}
				}
			}
		}
		
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < M ; ++c) {
				if(map[r][c] == 1) ans++;
			}
		}
		
		System.out.println(ans);
	}
	
	private static boolean attach(int[][] temp, int r, int c, int[][] sticker) {
		for(int i = 0 ; i < sticker.length ; ++i) {
			for(int j = 0 ; j < sticker[i].length ; ++j) {
				if(sticker[i][j] == 1) {
					if(temp[r + i][c + j] == 1) return false;
					temp[r + i][c + j] = sticker[i][j];
				}
			}
		}
		return true;
	}

	static int[][] rotate(int d, int[][] arr) {
		if(d == 0) return arr;
		
		int[][] result = new int[arr[0].length][arr.length];
		
		for(int i = 0 ; i < d ; ++i) {
			for(int r = 0 ; r < arr.length ; ++r) {
				for(int c = 0 ; c < arr[r].length ; ++c) {
					result[c][arr.length - 1 - r] = arr[r][c];
				}
			}
		}
		
		return result;
	}
	
	static int[][] copy(int[][] arr) {
		int[][] result = new int[N][M];
		
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < M ; ++c) {
				result[r][c] = arr[r][c];
			}
		}
		
		return result;
	}
	
	static int stoi(String s) {
		return Integer.parseInt(s);
	}
}