[백준] 3865 - 학회원

1. 문제

3865번: 학회원

2. 개요

각 테스트케이스별로

학회:학회원1,학회원2,학회원3 … 학회원N. 같은 형식의 입력이 주어진다.

학회원명에는 학회가 들어갈 수도 있는데, 이 경우 해당 학회의 학회원 전원을 의미한다.

이때 각 테스트케이스 별로 첫번째 입력된 학회의 학회원 수를 구하는 문제.

3. 코드 및 추가내용

학회명을 key, 학회원들을 value로 하는 딕셔너리를 먼저 만든 후,

입력받은 걸 잘 파싱해서 분류하여 딕셔너리를 갱신한다.

이때 첫 학회명은 출력값때문에 들고 있게 한다.

딕셔너리를 탐색하며 학회원에 학회명이 들어가있다면, 해당 학회의 학회원을 탐색해야 하므로 dfs를 사용, 인원을 채워나간다.

3-1. 시간초과

import sys

def dfs(society, s):
    tmp = s
    for m in society:
        if m in s_dict:
            dfs(s_dict[m], s)

        elif m not in s:
            tmp.add(m)

    return tmp

while True:
    n = int(sys.stdin.readline())

    if n == 0:
        break
    
    s_dict = dict()
    first = None
    for i in range(n):
        s, m = sys.stdin.readline().rstrip().split(':')
        if i == 0: first = s

        s_dict[s] = m[:-1].split(',')

    for s in s_dict:
        s_dict[s] = dfs(s_dict[s], set())

    print(len(s_dict[first]))

답은 잘 나오는데 시간초과.

집합에 학회를 아예 넣지 않고 학회원만 넣다보니 중복 인원을 탐색하는 경우가 많아서 실패한 것으로 보임.

3-2. AC

import sys

def dfs(society, s):
    tmp = s
    for m in society:
        if m in s:
            continue
        
        tmp.add(m)
        if m in s_dict:
            if set(s_dict[m]) in s:
                continue
            dfs(s_dict[m], s)

    return tmp

while True:
    n = int(sys.stdin.readline())

    if n == 0:
        break
    
    s_dict = dict()
    first = None
    for i in range(n):
        s, m = sys.stdin.readline().rstrip().split(':')
        if i == 0: first = s

        s_dict[s] = m[:-1].split(',')

    for s in s_dict:
        s_dict[s] = dfs(s_dict[s], set())
        for k in s_dict.keys():
            s_dict[s].discard(k)

    print(len(s_dict[first]))

집합이기 때문에 in의 원소 유무 체크 시간이 O(1)이므로 일단 학회, 학회원 가릴 것 없이 넣음.

탐색을 끝낸 후, 딕셔너리의 모든 키 값을 돌아보면서 집합에서 빼줌.

마지막으로 들고있던 첫 학회명의 학회원 수를 출력하면 끝.

다 쓰고 든 생각인데 딕셔너리를 다 탐색할게 아니라 그냥 첫 학회만 탐색해서 출력하면 되겠네? …

3-3. 첫 학회만 탐색

import sys

def dfs(society, s):
    tmp = s
    for m in society:
        if m in s:
            continue
        
        tmp.add(m)
        if m in s_dict:
            if set(s_dict[m]) in s:
                continue
            dfs(s_dict[m], s)

    return tmp

while True:
    n = int(sys.stdin.readline())

    if n == 0:
        break
    
    s_dict = dict()
    first = None
    for i in range(n):
        s, m = sys.stdin.readline().rstrip().split(':')
        if i == 0: first = s

        s_dict[s] = m[:-1].split(',')

    s_dict[first] = dfs(s_dict[first], set())
    for k in s_dict.keys():
        s_dict[first].discard(k)

    print(len(s_dict[first]))

잘 된다. 시간도 많이 빨라졌다.