[BOJ 16937] 두 스티커 (Java)

BOJ 16837 두 스티커

문제풀이

스티커가 나오면 바로 DP가 떠오르지만 이 문제는 아니다! 시간이 넉넉하고 메모리도 넉넉하다 완전탐색이 제격인 문제로 보인다.

• 스티커가 90도 회전 가능하지만 스티커의 사이즈가 주어진 형식으로 보아 모든 스티커가 직사각형의 자리를 차지하는 것을 알 수 있다. 따라서 하나의 스티커는 두 가지 방식으로 붙일수 있다.
• 그렇다면 최악의 경우에 100개의 스티커중 2개를 골라 스티커 마다 2가지 방향으로 붙일 수 있으므로 100C2 * 2 * 2로 무난하게 시간제한을 통과할 수 있다.
• 스티커를 붙일때 마다 돌리지말고 처음부터 붙일수있는 모든 형태의 스티커를 준비하면 편하다.
  • 그러나 90도 회전한 스티커는 원본 스티커와 같기 때문에 두 개의 스티커는 사용되었는지 확인하여 다시 사용하는 일이 없도록 해야한다. (방문체크)
• 아래에 구현한 코드에서는 Node Class를 스티커의 표현과 시작점의 좌표를 담는데 사용하였다.

구현코드

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

public class Main {
	
	static class Node {
		int id;
		int h, w;
		
		Node(int h, int w, int id){
			this.h = h;
			this.w = w;
			this.id = id;
		}
	}
	
	static boolean[][] map;
	static ArrayList<Node> list;
	static boolean[] isUsed;
	static int H, W, N;
	static int ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(br.readLine());
		
		ans = 0;
		map = new boolean[H][W];
		isUsed = new boolean[N];
		list = new ArrayList<>();

		for(int i = 0 ; i < N ; ++i) {
			st = new StringTokenizer(br.readLine());
			int h = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			list.add(new Node(h, w, i));
			list.add(new Node(w, h, i));
		}
		
		go(0, 0);
		
		System.out.println(ans);
	}

	private static void go(int cnt, int size) {
		if(cnt == 2) {
			ans = size > ans ? size : ans;
			return;
		}
		
		for(Node sticker : list) {
			if(isUsed[sticker.id]) continue;
			
			Node start = findStart(sticker);
			
			if(start == null) continue;
			
			attach(start, sticker, true);
			isUsed[sticker.id] = true;
			go(cnt + 1, size + sticker.h * sticker.w);
			isUsed[sticker.id] = false;
			attach(start, sticker, false);
		}
	}

	private static Node findStart(Node sticker) {
		for(int r = 0 ; r <= H - sticker.h ; ++r) {
			for(int c = 0 ; c <= W - sticker.w ; ++c) {
				if(map[r][c]) continue;
				
				boolean canAttach = true;
				for(int i = r ; i < r + sticker.h ; ++i) {
					for(int j = c ; j < c + sticker.w ; ++j) {
						if(map[i][j]) {
							canAttach = false;
							break;
						}
					}
					if(!canAttach) break;
				}
				if(canAttach) return new Node(r, c, -1);
			}
		}
		return null;
	}

	private static void attach(Node start, Node sticker, boolean type) {
		for(int r = start.h ; r < start.h + sticker.h ; ++r) {
			for(int c = start.w ; c < start.w + sticker.w ; ++c) {
				map[r][c] = type;
			}
		}
	}
}