[백준] 16937 두 스티커 - Brute Force / Java

• 문제 링크

16937번: 두 스티커

 

• 풀이 과정

예제 입력에 따르면 스티커의 형태는 직사각형이며,

스티커가 90도 회전 가능하므로 각각의 스티커 당 2가지 경우로 붙일 수 있음을 알 수 있다.

 

따라서 스티커 정보들을 입력받을 때 90도로 회전하거나 회전하지 않는 두 경우를

제네릭이 Node 클래스인 List 객체에 세로값과 가로값을 교차하여 저장하고,

각각의 스티커를 구분하는 id 값은 같게 저장한다.

 

이렇게 두 스티커를 조합하는 모든 경우의 수를 구하는데, List 객체에서 각각의 스티커 정보를 꺼내어

boolean 배열 visit 의 값에 따라 이미 사용한 스티커가 아니라면,

해당 스티커를 붙일 수 있는 시작점을 구해내기 위해 getRoot 함수를 실행한다.

 

map 배열에서 시작점이 될 수 있는 위치 중 해당 위치로부터 스티커만큼의 크기 중 방문한 곳이 없는 지,

즉 스티커가 교차되지 않는 곳을 찾아 적합한 시작점을 반환하며 없다면 null 값을 반환한다.

 

위의 조건이 만족하는 시작점이 존재할 경우, map 배열에 스티커의 크기만큼 방문 표시하고,

visit에 해당 스티커의 id 값을 통해 사용했음을 나타낸다.

이 후 재귀 호출 후 원 상태로 복귀하여 모든 경우의 수를 구하고,

구해진 두 스티커의 크기의 합의 최대값을 갱신하여 최종적으로 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	static int h, w, n, maxSize;
	static boolean[][] map;
	static boolean[] visit;
	static List<Node> list = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		h = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(br.readLine());

		map = new boolean[h][w];
		visit = new boolean[n];

		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));
		}

		recur(0, 0);

		bw.write(maxSize + "\n");
		bw.flush();
	}

	private static void recur(int size, int cnt) {
		if (cnt == 2) {
			maxSize = Math.max(maxSize, size);
			return;
		}

		for (Node rect : list) {
			if (visit[rect.id])
				continue;

			Node root = getRoot(rect);

			if (root == null)
				continue;

			put(root, rect, true);
			visit[rect.id] = true;
			recur(size + rect.h * rect.w, cnt + 1);
			put(root, rect, false);
			visit[rect.id] = false;
		}
	}

	private static Node getRoot(Node rect) {
		for (int y = 0; y <= h - rect.h; y++) {
			for (int x = 0; x <= w - rect.w; x++) {
				if (map[y][x])
					continue;

				boolean flag = true;
				loop: for (int i = y; i < y + rect.h; i++) {
					for (int j = x; j < x + rect.w; j++) {
						if (map[i][j]) {
							flag = false;
							break loop;
						}
					}
				}

				if (flag)
					return new Node(y, x, -1);
			}
		}

		return null;
	}

	private static void put(Node root, Node rect, boolean flag) {
		for (int i = root.h; i < root.h + rect.h; i++) {
			for (int j = root.w; j < root.w + rect.w; j++)
				map[i][j] = flag;
		}
	}

	private static class Node {
		int h, w, id;

		public Node(int h, int w, int id) {
			this.h = h;
			this.w = w;
			this.id = id;
		}
	}

}