[Python 3] BOJ 17720 마약수사대

https://www.acmicpc.net/problem/17220

 

마약수사대는 마약공급책을 잡고 싶어 한다.

마약의 원산지는 '다른 공급책에게 공급 받지 않는' 공급책이다.

여기서, 해당 문제는 마약 공급책들 중 마약을 공급받을 수 있는 공급책의 수를 구하는 문제이다.

 

해당 문제는 DAG (Directed Acyclic Graph)의 일종으로 볼 수 있다. 즉, cycle이 없지만, 방향성이 있는 간선들로 이루어져 있다.

따라서, 마약을 공급받지 않는 공급책들을 모두 저장받고, 해당 공급책들에 대해서 BFS를 실시하여 전달이 가능한 공급책들의 수를 세면 된다.

 

여기서 각 공급책의 이름이 대문자 알파벳으로 주어져 있다.

이들을 리스트의 index로 만들기 위해, 'A'의 아스키 코드에서 빼서 번호를 설정한다.

또한, 마약을 공급받은 적이 있는지의 여부를 received에서, BFS를 실시할 때의 방문 여부를 visited에서, 검거된 마약공급책을 저장하기 위한 infos를 설정하였다.

from collections import deque
n,m=map(int,input().split())
data=list([] for _ in range(n))
received=list(0 for _ in range(n))
for _ in range(m):
    a,b=input().split()
    a=ord(a)-ord('A')
    b=ord(b)-ord('A')
    data[a].append(b)
    received[b]+=1
st=received.index(0)
visited=list(0 for _ in range(n))
infos=list(map(lambda x: ord(x)-ord('A'),input().split()[1:]))
q=deque()
for i in range(n):
    if received[i] == 0 and i not in infos:
        q.append(i)
        visited[i] = True
while q:
    curr=q.popleft()
    for i in data[curr]:
        if i not in infos and not visited[i]:
            q.append(i)
            visited[i]=1
print(sum(1 for i in range(n) if visited[i] and received[i] != 0))