Wiki¶

1. 아래 그림에서 주어진 조건으로 grouping하여 두번째와 같은 결과를 만드는 문제입니다.
   1. [1,2,3,5], [4,11,7,8,9], [6,10] 각각 같은 조건을 가지고 있음
   2. 조건 : Package, Fluid, Material이 같고 연결된 아이템(물리적으로 연결되어 있으나 노즐이나 OPC에서는 끊김)
   3. 기능 : 아이템에서 연결된 아이템들은 찾을 수 있음(1번에 연결된 아이템은 2,3임)

알고리즘¶

1. [그림 1]을 다음과 같이 간략화 시킬수 있습니다.
2. all = [1,2,3,4,5,6,7,8,9,10,11,12]
3. 조건에 맞게 grouping합니다.
   

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

   • 위 루프는 무한 루프에 빠지지 않습니다.(최악의 경우 아이템 수만큼 패키지가 생성됨)
4. 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 만 비교하면 됩니다.
     어떤 구슬을 같은 색의 주머니에 넣기 위해 색깔을 비교할때 주머니에 있는 구슬 하나만 꺼내 비교하면 됩니다.(주머니에 있는 구슬들은 모두 같은 색깔이므로)

검증¶