[PS] BOJ 3865 / 학회원

Minjun Kim

03 Sep 2025 • 2 min read

Thumbnail: Photo by Linda Gerbec (Unsplash)

문제 링크: https://www.acmicpc.net/problem/3865

그래프 탐색을 응용하는 문제입니다.

풀이

파싱 + 그래프 탐색

파싱을 통해 유향 그래프를 만들어낸 뒤, 그래프 탐색으로 진출 차수가 0인 정점의 개수를 세면 됩니다.

1) 파싱

먼저, 입력 데이터는 다음과 같이 구성됩니다.

N
academy_name:member1,member2,...,memberK.
... (repeated N-1 times)

입력 데이터 구조

$N$은 입력으로 주어지는 학회의 수이고, 각 학회의 입력에 주어지는 학회원 명단은 최대 10명입니다. 각 멤버의 이름은 ,로 구분되며, 각 줄의 끝에는 마침표가 붙습니다.

edges = {}
text = input().rstrip()[:-1] # 마지막 1글자는 마침표이므로 제외
academy_name, member_names = text.split(":") # 학회 이름과 학회원 명단 분리
edges[academy_name] = member_names.split(",") # 학회원 이름 분리

학회 이름과 멤버 이름 분리하기

정규식을 사용해도 되지만, 간단한 구조를 고려해 문자열을 쪼개는 방식으로 구현했습니다.

각 학회에 대한 입력은 (학회명) → (학회원)의 유향 그래프 형태로 저장됩니다.

그래프 탐색

이후, 입력을 파싱해 만든 유향 그래프에 대해 그래프 탐색을 진행해주면 됩니다. 저는 BFS로 진행했습니다.

cnt = 0
visited = {}
# BFS to resolve member count
queue.append(target_academy) # 첫 번째로 주어진 학회의 이름에 대해 학회원 수 구하기
while queue:
    name = queue.popleft()
    for m in edges[name]:
        if not visited.get(m, False): # 아직 방문하지 않은 정점에 대해
            visited[m] = True
            if edges.get(m, None) is not None and len(edges[m]) > 0: # 진출 차수가 0이 아니라면, 학회 이름이므로 큐에 추가
                queue.append(m)
            else: # 진출 차수가 0인 정점은 학회원의 이름이다.
                cnt += 1
print(cnt)

BFS

전체 코드

from collections import deque
input = open(0).readline

cnt = 0
edges = {}
visited = {}
target_academy = ""
queue = deque()
while True:
    N = int(input())
    if N == 0:
        break

    cnt = 0
    edges.clear()
    visited.clear()
    for i in range(N):
        text = input().rstrip()[:-1]
        academy_name, member_names = text.split(":")
        if i == 0:
            target_academy = academy_name
        edges[academy_name] = member_names.split(",")

    # BFS to resolve member count
    queue.append(target_academy)
    while queue:
        name = queue.popleft()
        for m in edges[name]:
            if not visited.get(m, False):
                visited[m] = True
                if edges.get(m, None) is not None and len(edges[m]) > 0:
                    queue.append(m)
                else:
                    cnt += 1
    print(cnt)

solution.py