상점가격점검 기능이 고장남

[solo5star]

PocketMine-MP 의 Crafting API가 업데이트되면서 이전에 구현하였던 알고리즘을 더 이상 쓸 수가 없습니다. 새로운 알고리즘을 짜야 하지만 아직까진 실력이 부족하여 해결이 어려울 것 같습니다. 해결이 정말 불가능한 경우 기능 자체를 없애는 것도 고려하고 있습니다.

번외로, 골머리를 앓고 있는 알고리즘 구현을 문제로 만들어보았으니 관심있으신 분들은 읽어보세요.

---

개요

최근에 서버를 운영하기 시작한 어드민은 상점 플러그인을 서버에 넣어, 몇몇 아이템에 판매가/구매가를 설정하여 상점을 구성했다.

상점을 구성해놓고 보니 조합법을 악용하여 차액을 크게 벌어들일 수 있는 사실을 확인했다. 혹여나 다른 아이템도 악용이 가능하지 않을까 걱정한 끝에 아래와 같이 알고리즘을 구현하기로 하였다.

목적

어드민은 유저들이 상점에서 싼 가격으로 재료(Ingredients)를 모아, 비싼 가격으로 되파는 행위, 즉 조합법을 악용하는 것을 막고싶다.

정의

• Item - Minecraft 내의 아이템에 해당한다. 판매가와 구매가를 가질 수 있다.
• Recipe - 여러개의 Item으로 새로운 Item을 만들 수 있는 규칙을 정의, 즉 조합법이다.
• Ingredients - Recipe 에서 결과물(Result)을 만들기 위해 필요한 재료, Item의 배열이다.
• Result - Recipe 에서 조합 결과물(Result)로 나오는 아이템, Item의 배열이다.

주어지는 정보

• Item 들의 판매가와 구매가가 주어진다.
  • 판매 또는 구매 불가인 경우 가격은 -1로 주어진다.
  • 구매가는 판매가보다 같거나 작다.
• Recipe 배열이 주어진다.

구현

Recipe 배열로 방향 그래프(Directed Graph)를 구성한다.

• 각 노드는 Item 의 배열이다.
• 진입 노드는 Recipe의 재료(Ingredients)
• 진출 노드는 Recipe의 결과(Result)
• Item이 구매 불가인 경우 순회(Ordering)하여 가장 싸게 구매할 수 있는 가격을 구해야 한다.

그래프를 구성한 후

• 사이클(Cycle)이 발생할 수도 있다. 이 경우 사이클을 가지는 부분 그래프의 모든 노드들은 똑같은 판매가를 가져야 한다. 그렇지 않은 경우 부분 그래프의 모든 노드들을 출력한다.
• 진입 노드의 구매가가 진출 노드의 판매가보다 적으면 출력한다.

방향 그래프(Directed Graph)의 예시

+는 간선(Vertex)이 향하는 방향을 표기한 것이다.

[solo5star]

문제에 잘못된 내용이 있다면 언제든지 말씀해주세요.

[solo5star]

문제의 난해한 부분입니다. 조합 결과(Result) 아이템이 하나가 아니기 때문에, 위와 같은 상황 발생시 최저가격(Minimal cost) 판단이 어렵습니다.

[solo5star]

마인크래프트의 기본 조합법에서 결과(Result) 아이템이 두 종류 이상인 조합법은 Cake밖에 없습니다. 그러면 Cake만 빼고 풀면 안되나? 하지만 이런 경우를 생각해볼수도 있습니다.

개발자가 자신만의 Recipe를 추가할 수도 있습니다. 이 경우 결과(Result) 아이템은 케이크보다 더 많을 수도 있습니다. 두 개 혹은 세 개, 네 개, 다섯 개가 될 수도 있습니다.