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

 

문제

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

문제풀이

⭐  가장 중요한 것 은 Rotation을 어떻게 할 것 인지가 중요하다. 나는 아래와 같이 그림을 그리면서 로테이션 했을 때 (y, x) 좌표가 어떤식으로 변화하는지 확인하였다. 이 과정에서 Rotation을 구현할 수 있었고 그 외에는 시뮬레이션을 돌려가며 순서대로 구현하면 문제없이 풀 수 있다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {	
	public static int N, M, K, res;
	public static int[][] map;
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	String[] inputs = br.readLine().split(" ");
    	
    	N = Integer.parseInt(inputs[0]);
    	M = Integer.parseInt(inputs[1]);
    	K = Integer.parseInt(inputs[2]);
    	
    	map = new int[N][M];
    	
    	for(int k = 0; k < K; k++) {
    		// 스티커 크기
    		String[] sizeInfo = br.readLine().split(" ");
    		int h = Integer.parseInt(sizeInfo[0]);
    		int w = Integer.parseInt(sizeInfo[1]);
    		int[][] sticker = new int[h][w];
    		
    		for(int i = 0; i < h; i++) {
    			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    			for(int j = 0; j < w; j++) {
    				sticker[i][j] = Integer.parseInt(st.nextToken());
    			}
    		}
    		
    		attach(sticker);
    	}
    	
    	for(int i = 0; i < N; i++) {
    		for(int j = 0; j < M; j++) {
    			if(map[i][j] == 1) res++;
    		}
    	}
    	
    	System.out.println(res);
    }
    
    // 스티커 붙이기
    public static void attach(int[][] s) {
    	for(int r = 0; r < 4; r++) {
    		for(int i = 0; i < N; i++) {
        		for(int j = 0; j < M; j++) {
        			if(!isValid(i, j, s)) continue;
        			int maxX = j + (s[0].length);
        			int maxY = i + (s.length);
        			for(int y = i; y < maxY; y++) {
        				for(int x = j; x < maxX; x++) {
        					if(s[y-i][x-j] == 1) map[y][x] = s[y-i][x-j];
        				}
        			}
//        			print();
        			return;
        		}
        	}
    		s = rotate(s.length, s[0].length, s);
    	}
    }
    
    public static void print() {
    	for(int i = 0; i < N; i++) {
    		for(int j = 0; j < M; j++) {
    			System.out.print(map[i][j]);
    		}
    		System.out.println();
    	}
    	System.out.println();
    }
    
    // 검증하기
    public static boolean isValid(int y, int x, int[][] s) {
    	// 크기
    	int maxX = x + (s[0].length);
    	int maxY = y + (s.length);
    	
    	// 범위 초과
    	if(maxX > M || maxY > N) return false;
    	
    	for(int i = y; i < maxY; i++) {
    		for(int j = x; j < maxX; j++) {
    			if(map[i][j] != 0 && s[i-y][j-x] == 1) return false;
    		}
    	}
    	
    	return true;
    }
    
    // 스티커 회전하기
    public static int[][] rotate(int h, int w, int[][] s){
    	int[][] r = new int[w][h];
    	
    	for(int i = 0; i < h; i++) {
    		for(int j = 0; j < w; j++) {
    			r[j][(h-1)-i] = s[i][j];
    		}
    	}
    	
    	return r;
    }
}