Qualification Round. Problem 1 Chemical Reactions

화학 반응식과 초기 substrate로 최종적으로 생성되는 물질들을 구하는 문제이다.

from functools import reduce
import sys
input = []
for line in sys.stdin:
  input.append(line.strip())

# with open('2') as f:
#     input = f.read().strip().split('\n')

chemicals = set(input[0].split(' '))
reactions = list(map(lambda reaction: list(map(lambda side: side.split('+'), reaction.split('->'))), input[1:]))

num_chemicals = len(chemicals)

while True:
    unused = []
    for reaction in reactions:
        left = set(reaction[0])
        if left.intersection(chemicals) == left:
            for ingredient in reaction[1]:
                chemicals.add(ingredient)
        else:
            unused.append(reaction)
    if len(chemicals) == num_chemicals:
        break;
    else:
        reactions = unused
        num_chemicals = len(chemicals)

print(' '.join(chemicals))

Easy버전는 위와같이 간단하게 풀었다.
단순하게 반응물과 생성물로 나눈후 반응식을 계속해서 순회하며 현재 존재하는 반응물들이 해당 반응식의 반응물로 존재하면 생성물을 현재 반응물 set에 추가하고 반응식 리스트를 모두 순회해도 현재 반응물 set의 크기에 변화가 없다면 종료한다.

하지만 위와 같은 단순한 방식으로는 Hard버전을 통과할수는 없었다. Easy는 10^3개의 reactions들이지만 Hard버전은 10^5이기때문에 Time limit에 걸렸다.

결국 이런식으로 수정했다.

import sys
input = []
for line in sys.stdin:
    input.append(line.strip())

# import time
#
# with open('Q1') as f:
#     input = f.read().strip().split('\n')

chemicals_set = set()
chemicals_queue = set(input[0].split(' '))
reactions = list(map(lambda reaction: list(map(lambda side: set(side.split('+')), reaction.split('->'))), input[1:]))
reactions_dict = {}
for reaction in reactions:
    for substrate in reaction[0]:
        try:
            reactions_dict[substrate].append(reaction)
        except:
            reactions_dict[substrate] = [reaction]
while len(chemicals_queue) > 0:
    cur_substrate = chemicals_queue.pop()
    chemicals_set.add(cur_substrate)
    try:
        target_reactions = reactions_dict[cur_substrate]
    except:
        continue
    for target_reaction in target_reactions:
        if target_reaction[0].issubset(chemicals_set):
            chemicals_queue = chemicals_queue.union(target_reaction[1] - chemicals_set)
print(' '.join(chemicals_set))

reactions_dict = {}
for reaction in reactions:
    for substrate in reaction[0]:
        try:
            reactions_dict[substrate].append(reaction)
        except:
            reactions_dict[substrate] = [reaction]

reaction의 반응물을 dictionary의 key로 사용하여 해당 물질을 반응물로 사용하는 식들의 리스트들을 모은다.

reactions_dict = {}
for reaction in reactions:
    substrate_key = '_'.join(sorted(reaction[0]))
    try:
        reactions_dict[substrate_key] = reactions_dict[substrate_key].union(reaction[1])
    except:
        reactions_dict[substrate_key] = set(reaction)

물론 위와같이 reaction의 반응물을 set로하여 그것을 key로 사용하여 dictionary에 저장하면 반응물 목록만 알고있으면 결과물을 상수시간안에 구할 수 있지만 우리가 가지고 있는건 현재 존재하는 물질들의 목록이지 현재 반응에 사용될 물질의 목록이 아니기 때문에 결국 반응할 substrate들의 조합들을 전부 순회해야 하기 때문에 좋은 선택이 아니다. (왜 이런말을 하냐면 그렇게 했다가 timeout났기 때문에...)

while len(chemicals_queue) > 0:
    cur_substrate = chemicals_queue.pop()
    chemicals_set.add(cur_substrate)
    try:
        target_reactions = reactions_dict[cur_substrate]
    except:
        continue
    for target_reaction in target_reactions:
        if target_reaction[0].issubset(chemicals_set):
            chemicals_queue = chemicals_queue.union(target_reaction[1] - chemicals_set)

그 뒤는 단순한데 반응으로 생성된 새로운 물질들은 chemicals_queue에 넣고 하나씩 꺼낸다. chemicals_queue에서 꺼낸 물질을 key로하는 reaction list, 즉 해당 물질을 포함하는 반응식을 reactions_dict에서 꺼낸 후 해당 반응식이 반응 가능한지 본후 반응이 가능하다면 생성물을 다시 queue에 넣는다. chemicals_queue가 set인 이유는 이미 포함돼있으면 중복해서 넣는 것을 방지하기 위함이다.

그런데 위 코드는 Hard버전의 15번 test set에서 timeout이 난다. 뭐가 문젠가 로컬에서 돌려보니 2.3초 정도 걸렸다... 파이썬... 댓글에는 파이썬으로도 통과가 가능하다는데... 나는 그다지 믿지 않는다. 전에 어떤 온라인 문제푸는곳에서 나는 파이썬으로 O(n^2logn)으로 풀고 친구는 단순하게 자바로 O(n^3)으로 풀었는데 나는 타임리밋 20초에서 10초만에 통과하고 친구는 2초정도밖에 걸리지 않았던 기억이 있다. 위 코드도 단순하게

        if target_reaction[0].issubset(chemicals_set):
            chemicals_queue = chemicals_queue.union(target_reaction[1] - chemicals_set)

부분을

        if len(chemicals_set - target_reaction[0]) == len(chemicals_set) - len(target_reaction[0]):
            chemicals_queue = chemicals_queue.union(target_reaction[1] - chemicals_set)

으로 subset을 검사하는게 아닌 length를 검사하는것으로 바꾸면 13번 테스트가 20초 정도 걸리는걸 볼 수 있다. 어쨌든 언어에 관계없이 2초가 타임리밋이고 파이썬으로 2.3초만에 끝나면 사실상 시간복잡도 이슈는 없는것이므로 그냥 이정도로만 끝내도록 하겠다.