조건에 맞는 아이템들끼리 그룹 만들기

아래 그림에서 주어진 조건으로 grouping하여 두번째와 같은 결과를 만드는 문제입니다.

• [1,2,3,5], [4,11,7,8,9], [6,10] 각각 같은 조건을 가지고 있음

• 조건 : Package, Fluid, Material이 같고 연결된 아이템(물리적으로 연결되어 있으나 노즐이나 OPC에서는 끊김)
• 기능 : 아이템에서 연결된 아이템들은 찾을 수 있음(1번에 연결된 아이템은 2,3임)

---

알고리즘

[그림 1]을 다음과 같이 간략화 시킬수 있습니다.

all = [1,2,3,4,5,6,7,8,9,10,11,12]

조건에 맞게 grouping합니다.

packages = []
while all:
  item = all.pop()
  package = group(item)  
  packages.append(package)
  package.consume(all)

• 위 루프는 무한 루프에 빠지지 않습니다.(최악의 경우 아이템 수만큼 패키지가 생성됨)

group 클래스

class group:
  def __init__(self, item):
    self.members = [item]

  def consume(self, all):
    """group을 구성한다""" 
    stack = self.members
    while stack:
      item = stack.pop()
      connected_items = self.get_connected_items(item, all)
      for connected in connected_items:
         if connected is Equipment or connected is OPC:
           all.remove(connected)
           continue

         if self.members[0].package == connected.package and self.members[0].fluid == connected.fluid and self.members[0].material == connected.material:
           stack.append(connected)
           self.members.append(connected)
           all.remove(connected)

  def get_connected_items(self, item, all) -> list:
    """item에 연결된 아이템들 중 all에 있는 것을 리턴한다""" 
    return [connected for connected in item.connecteds if connected in all]

• member 하나와 connected 만 비교하면 됩니다.
  어떤 구슬을 같은 색의 주머니에 넣기 위해 색깔을 비교할때 주머니에 있는 구슬 하나만 꺼내 비교하면 됩니다.(주머니에 있는 구슬들은 모두 같은 색깔이므로)

---

검증