[💬] 인벤토리 정렬 알고리즘

[ㅁㄴㅇㄹ(121.181)]

우선 몇가지 전제가 있다.

1. 인벤토리는 격자형으로 나뉘어져 있으며 그 테두리는 사각형의 형상을 띄고 있다.

2. 아이템 역시 테두리는 사각형의 형상을 띄고 있다.

3. 아이템들은 서로 겹칠 수 없다.

이러한 전제 속에서 나는 우선 한가지를 관찰할 수 있었는데, 이 문제(https://www.wikiwand.com/en/Polygon_covering#/Covering_a_rectilinear_polygon_with_rectangles)를 풀 수 있다면 알고리즘의 나머지는 매우 간단하다는 것이었음. 

문제 자체를 설명하는건 간단함. 테두리 선이 오직 수평이거나 수직인 다각형이 하나 있을 때 서로간에 겹칠 수 있는 가장 적은 숫자의 사각형을 통해 그 다각형의 전체를 덮는 문제임.

왜 이 문제가 인벤토리 정렬 알고리즘을 푸는데 연관이 있냐면, 이 문제를 풀고나면 사각형들의 집합을 하나 얻게 되잖아? 그 사각형들의 합은 원 다각형을 덮고. 여기서 이 다각형을 인벤토리 안에 있는 빈 공간들의 합이라고 보자. 그러면 이 사각형들은 인벤토리 안에 아이템들을 놓을 수 있는 각기 다른 위치와 그 위치에 놓을 수 있는 아이템의 최대 크기를 나타내는 것이라 볼 수 있음. 그걸 알아내고나면 인벤토리 정렬 알고리즘은, 인벤토리를 비우고, 인벤토리 안에 있던 아이템들을 어느 순서대로 다시 인벤토리에 집어넣고, 어느 사각형에 아이템을 넣을 것인가, 이 정도 문제들만 남음.

나는 이 문제를 이 논문(https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4576)을 참고해서 풀음. 이 논문에서 제시하는 알고리즘은 위에 말한 문제를 휴리스틱(heuristic)으로 푸는데, 핵심 원리는 진짜 간단함.

1. 다각형의 형상이 주어지면 다각형이 맞는 곳과 다각형이 아닌 곳으로 나눈다. 그러니까 네모난 도넛의 형상이 주어지면 그 중 도넛 부분은 다각형이 맞고 그 테두리와 중심의 구멍은 다각형이 아닌 곳인거지. 편의상 앞으로 다각형이 맞는 곳은 '다각형'이라 부르고 다각형이 아닌 곳은 '구멍'이라 칭하겠음.

2. x좌표는 같고 y좌표만 다른 두개의 구멍 사이에 최소 한 칸 이상의 다각형이 있다면 구멍 사이에 있는 모든 다각형은 하나의 '줄'을 형성한다.

3. 다각형 안에 존재하는 모든 줄을 찾아서 하나의 집합에 모아놓는다.

4. 모든 줄 마다 그 줄을 왼쪽으로 그 다음에는 오른쪽으로 밀어서 만들 수 있는 가장 큰 사각형을 모아놓는다.

5. 완전히 겹치는, 그러니까 모든 꼭짓점의 위치가 동일한 사각형들은 하나만 남기고 나머지는 없앤다.

6. 이렇게 얻어낸 사각형들은 다각형의 형상을 당연히 모두 덮고, 최적의 해와 최대 오직 약간의 차이점만을 가진다.

이렇게 풀고 나면 남은 것은 간단함.

1. 인벤토리 안에서 모든 아이템을 비운다.

2. 아이템들을 크기에 따라 정렬시킨다.

3. 크기가 큰 순서대로 아이템을 인벤토리에 다시 집어넣는다.

4. 아이템을 인벤토리에 집어넣을 때, 

4.1. 인벤토리 안에 아이템이 있는 곳과 인벤토리 가장자리 바깥을 구멍으로 지정하고 아이템이 없는 곳을 다각형으로 지정한 다음 바로 위의 알고리즘을 통해 그걸 덮는 사각형들을 계산해낸다.

4.2. 아이템을 집어넣을 수 있는 사각형들 중 가장 크기가 작은 것을 골라 그 사각형의 왼쪽 위 구석에 아이템을 집어넣는다.

4.3. 새로 아이템이 들어간 곳을 구멍으로 지정한 후 다음 아이템에 똑같이 반복.

끗.

[익명(223.62)]

ㅊㅊ

[데쿠(hhw000)]

몬..몬가 일어나고 있는것임

[김메가(scw973108)]

[모노모노모노(monosw2000)]

그냥 인벤토리를 그리드 기반으로 만들고, 그리드에 해당하는 bool 2차원 배열을 만든 다음에 큰 놈부터 쑤셔넣으면 되는거 아닌가오?

[ㅁㄴㅇㄹ(121.181)]

이것도 인벤토리가 그리드이긴 한데 여하튼 그것도 한 방법이지만 다음 이유들 때문에 이렇게 함. 우선, 그렇게 하면 그 과정에서 일어날 수 있는 여러 특수한 사례들을 하나하나 직접 손봐야할거 같았음. 예를 들자면 3x3, 3x2, 1x3, 3x1, 이렇게 4개의 아이템이 있다고 하자. 3x3이 가장 크니 그게 가장 먼저 집어넣어질테고, 그 다음 큰 것은 3x2이니 3x3의 옆에 3x2이 놓아지겠지. 그 다음으로 1x3이 3x2 옆에 놓아진다고 하자. 그럼 이 경우에 마지막 3x1 아이템은 어디에 놓여져야 하는가가 내 생각에 문제가 될거 같았음. 3x3과 1x3 사이 3x2 바로 아래에 놓여져야 하는가, 아니면 1x3 옆에 놓여져야 하는가.

[ㅁㄴㅇㄹ(121.181)]

이 간단한 예는 큰 놈부터 집어넣는다는 말이 실제 알고리즘으로 적용하기에는 너무 두루뭉실하다는 것을 보여줌. 큰 놈부터 정확히 어떻게 집어넣을 것인가. 내 알고리즘도 보면 나오지만 큰 놈부터 집어넣음. 차이점은 큰 놈부터 정확히 어떻게 집어넣느냐가 역시 포함되어 있다는 것이겠지.

[ㅁㄴㅇㄹ(121.181)]

그 다음 이유는 내가 이것을 만들 때 달성하고자 한 목표가 인벤토리 정리하는 것에 국한되지 않고 모종의 인벤토리와 모종의 아이템이 주어졌을 때 그 아이템을 인벤토리에 자동으로 어떻게 집어넣는가, 이것 역시 포함하고 있다는 것임. 아이템 하나 집어넣을 때마다 매번 인벤토리를 통채로 정리할 수는 없잖아? 이 알고리즘을 조금만 응용하면 인벤토리를 통채로 정리하지 않고도 모종의 아이템을 최적의 장소에 집어넣는 목적으로 쓸 수 있음.

[ㅁㄴㅇㄹ(121.181)]

마지막 이유, 이렇게 짜는 것이 깔끔하니까. 확장성 있고 일반화 되어 있으며 다용도로 쓸 수 있는 알고리즘을 만들어 그걸 코드로 구현하는게 더 깔끔함. 나중에 확장 및 유지를 고려하면 이게 더 나은 방식이라 판단되었음.

[모노모노모노(monosw2000)]

큰놈부터라는게, 그냥 가로 곱하기 세로 값이 큰 놈 순서로 정렬이지. 어차피 게임이라는 특성상, 정렬이 이쁘고 잘 되냐보다도 얼마나 빠르게 되냐의 문제인데 그러면 그리드로 만들면 자연수 좌표값을 가지는 사각형 도형들로 만들고 2차원 배열로 만든 다음에 집어넣으면 되지 싶음.

[모노모노모노(monosw2000)]

이 알고리즘을 다른데에 이용할 수 있다는 점에서는 나도 동의하고, 아틀라스 시트 만드는건 이런 알고리즘으로 만들었는데 인벤토리는.. 음.

[모노모노모노(monosw2000)]

그리고 기획적으로 해결할 수도 있는게 많음. 인벤토리의 크기가 완전 정사각형인 경우보다는, 어느쪽으로 더 긴지를 보고, 대부분의 아이템이 그쪽으로 길도록 만들어주면 됨. 알고리즘을 손보는게 아니라 인풋값을 인위적으로 손 보는 것인데, 10x15짜리 인벤토리의 경우 아이템의 크기가 가로보다 세로가 언제나 같거나 길게 만들어주면 정렬도 쉬움여.

[ㅁㄴㅇㄹ(121.181)]

알고리즘으로 정리해서 올려줄 수 있음?