URL 복사
카카오톡 공유하기상자 쌓기 알고리즘
문제
어느 화창한 봄날, 당신은 패트릭을 만나러 가고 있다.
패트릭은 친한 친구이자 과거 범죄 파트너로 프로그래밍 대회에 돈을 걸었다가 전 재산을 탕진하고 다시 한번 한탕을 노리고 있다.
그런 그가 당신의 도움을 필요로 한다.
비록 당신은 범죄의 세계를 떠났지만 말이다.
당신은 예전의 범죄 생활로 돌아갈 생각이 전혀 없었기에 처음에는 좀 꺼려했지만 일단 그의 계획을 들어보는 것은 큰 문제가 없다고 생각하게 되었다. <br/>
<br/>
근처 창고에 고가의 기물들이 담긴 상자들이 있으며 패트릭은 기물들을 최대한 많이 훔치려고 계획하고 있다.
이를 위해서 건물로 들어갈 방법을 찾아야 하고, 경비원들을 처리해야 하며 복잡하게 얽힌 레이저빔을 건드리지 않고 지나가야 한다.
흔히 생각하는 도둑질 패턴대로 말이다.
하지만 창고의 가장 중요한 부분이 패트릭이 무력화시킬 수 없는 경비 시스템으로 보호 되고 있다.
바로 이 곳이 패트릭이 당신의 도움을 필요로 하는 곳이다.
기물은 정육면체의 대형 운송상자 안에 보관되어 있으며 상자들은 모두 크기가 같다.
상자들은 차곡차곡 쌓여 있으며 3차원 격자 형태를 띠고 있다.
경비 시스템은 3대의 카메라(정면 카메라, 측면 카메라, 상단 카메라)를 이용하여 한 시간에 한번씩 쌓여진 상자의 사진을 찍는다.
정면 카메라로 찍은 이미지는 각 열에서 가장 높이가 높은 상자 더미의 높이를 보여주고, 측면 카메라로 찍은 이미지는 각 행에서 가장 높이가 높은 상자 더미의 높이를 보여준다.
또한 상단 카메라의 이미지는 쌓여진 상자 더미가 비어있는 곳이 있는지 보여준다.
만약 이 이미지 중 어떠한 것에든지 변화가 감지되면 경보 시스템은 경고음을 울린다.
<br/>
패트릭이 건물 내부로 잠입하고 나면 그는 각 더미의 높이를 파악하여 당신에게 보내줄 것이다.
그림 C.1 은 격자의 가능한 형태 중 하나를 보여주며 각 카메라가 찍고 있는 이미지를 보여준다.<br/>
<br/>
측면 카메라 → <img alt="" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/CTBSQH181224235517.JPG" style="width:500px">
↑ 정면 측면 상단<br/>
전면 카메라<br/>
<br/>
그림C.1: 높이표와 이를 찍은 카메라 이미지들<br/>
패트릭은 가능한 많은 상자를 훔치고 싶다. 경보 시스템을 무력화시킬 수는 없기 때문에 시스템을 속이는 방식을 택하기로 했다.
남아있는 상자들을 더미에 잘 정리하여 쌓아서 다음 카메라 이미지에서는 변화가 나타나지 않도록 하는 것이다.
위의 예시에서는 9개의 상자를 훔치는 것이 가능하다.
그림 C.2 는 상자를 훔치고 난 후 가능한 격자판을 보여주며 이는 경비 시스템상으로는 동일한 것으로 보여지게 된다.
<br/>
<br/>
<img alt="" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/G0MWDE181224235517.JPG" style="width:150px"><br/>
<br/>
그림C.2: 물건을 훔친 후 높이 격자판<br/>
패트릭은 경비 시스템에 걸리지 않고 훔칠 수 있는 상자의 최대 개수를 알아내 달라고 당신에게 요청했다.
이 마지막 작업을 완성할 수 있도록 그를 도와주겠는가?
<br/>
입력
1 4 0 5 2
2 1 2 0 1
0 2 3 4 4
0 3 0 3 1
1 2 2 1 1
50 20 3
20 10 3
출력
9
30
소스코드
import java.util.Arrays;
public class BoxAlgo {
// public static final int INPUT[][] = {
// { 1, 4, 0, 5, 2 },
// { 2, 1, 2, 0, 1 },
// { 0, 2, 3, 4, 4 },
// { 0, 3, 0, 3, 1 },
// { 1, 2, 2, 1, 1 } };
// public static final int INPUT[][] = { { 1, 0, 0, 5, 2 }, { 2, 4, 2, 0, 1 }, { 0, 2, 3, 5, 4 }, { 0, 7, 0, 5, 1 },
// { 3, 3, 3, 3, 6 }};
public static final int INPUT[][] = { {3,3,2,2,2},{2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2}};
public static int top[][];
public static int left[];
public static int front[];
public static void main(String[] args) {
int leng1 = INPUT.length;
int leng2 = INPUT[0].length;
top = new int[leng1][leng2];
left = new int[leng1];
front = new int[leng2];
init(INPUT, top, left, front);
int[][] output = new int[leng1][leng2];
int[][] ntop = new int[leng1][leng2];
int[] nleft = new int[leng1];
int[] nfront = new int[leng2];
for (int i = 0; i < leng1; i++) {
for (int j = 0; j < leng2; j++) {
if (j == 0) {
output[i][j] = left[i];
} else {
output[i][j] = 1;
}
}
}
int leftMax = getMaxValueIndex(left);
int frontMax = getMaxValueIndex(front);
boolean[] used = new boolean[leng2];
for (int i = 0; i < leng1; i++) {
int val = left[i];
for (int j = 0; j < leng2; j++) {
if (left[i] == front[j]) {
used[j] = true;
output[i][0] = 1;
output[i][j] = val;
break;
}
//사용하지 않은 MAX Value는 가장 큰 front 뒤로
if (j == leng2 - 1) {
output[i][0] = 1;
output[i][frontMax] = val;
break;
}
}
}
//사용하지 않은 MAX Value는 가장 큰 left 뒤로
for (int i = 0; i < used.length; i++) {
if (used[i] != true) {
output[leftMax][i] = front[i];
}
}
//TOP 처리
for (int i = 0; i < leng1; i++) {
for (int j = 0; j < leng2; j++) {
if (top[i][j] == 0) {
if (output[i][j] == 1) {
output[i][j] = 0;
}
}
}
}
for (int i = 0; i < leng1; i++) {
for (int j = 0; j < leng2; j++) {
if (top[i][j] == 0) {
if (output[i][j] != 0) {
insert(output, i, j, output[i][j]);
}
}
}
}
//
init(output, ntop, nleft, nfront);
print("INPUT", INPUT);
print("OUTPUT", output);
pirnt("LEFT", left);
pirnt("NEW LEFT", nleft);
pirnt("FRONT", front);
pirnt("NEW FRONT", nfront);
System.out.println("======== RESULT =======");
System.out.println("INPUT SUM\t" + getAllValueSum(INPUT));
System.out.println("OUTPUT SUM\t" + getAllValueSum(output));
System.out.println("RESULT\t\t" + (getAllValueSum(INPUT) - getAllValueSum(output)));
}
public static void init(int[][] input, int top[][], int left[], int front[]) {
int l1 = input.length;
int l2 = input[0].length;
//Init Top
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (input[i][j] != 0) {
top[i][j] = 1;
}
}
}
//Init Left
int max;
for (int i = 0; i < l1; i++) {
max = -1;
for (int j = 0; j < l2; j++) {
if (input[i][j] > max) {
max = input[i][j];
}
}
left[i] = max;
}
//Init Front
for (int i = 0; i < l2; i++) {
front[i] = -1;
}
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (input[i][j] > front[j]) {
front[j] = input[i][j];
}
}
}
}
public static void insert(int[][] output, int i, int j, int val) {
boolean includeLargeValue;
//세로 비교
includeLargeValue = false;
for (int k = 0; k < left.length; k++) {
if (output[k][j] >= val && k != i) {
includeLargeValue = true;
break;
}
}
if (!includeLargeValue) {
for (int k = 0; k < left.length; k++) {
if (left[k] > val) {
if (output[k][j] == 1) {
output[k][j] = val;
break;
}
}
}
}
//가로 비교
includeLargeValue = false;
for (int k = 0; k < front.length; k++) {
if (output[i][k] >= val && k != j) {
includeLargeValue = true;
break;
}
}
if (!includeLargeValue) {
for (int k = 0; k < front.length; k++) {
if (front[k] > val) {
if (output[i][k] == 1) {
output[i][k] = val;
break;
}
}
}
}
//SET 0;
output[i][j] = 0;
}
public static int getMaxValueIndex(int[] arr) {
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > arr[index]) {
index = i;
}
}
return index;
}
public static int getAllValueSum(int[][] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
sum += arr[i][j];
}
}
return sum;
}
public static void print(String title, int[][] arr) {
System.out.println("=========" + title + "========");
for (int i = 0; i < arr.length; i++) {
System.out.println(Arrays.toString(arr[i]));
}
System.out.println("");
}
private static void pirnt(String title, int[] arr) {
System.out.println("=========" + title + "========");
System.out.println(Arrays.toString(arr));
System.out.println("");
}
}
<br/>
<br/>
