[백준 | Python] #24526 - 전화 돌리기

24526번: 전화 돌리기

 

아이디어

문제를 단방향 그래프로 표현할 수 있다.

어떤 부원이 두 번 이상 전화를 받게 되려면, 그 부원이 어떤 사이클에 존재해야 한다.

더불어 사이클에 존재하는 부원들에게 전화를 넘겨줄 수 있는 부원들과, 그 부원들에게 넘겨줄 수 있는 또다른 부원들과, ... 재귀적으로 이런 부원들은 잠재적으로 어떤 부원이 두 번 이상 전화를 받게 할 수 있다.

반면, 그렇지 않은 부원이 다시 사이클에 진입 시킬 수 없는 부원이고 아래 그래프에서는 6, 7, 8번 정점에 해당한다.

 

구현

6, 7, 8번 정점과 같은 정점을 찾자.

DFS와 유사한 방식으로 자식의 리턴값을 이용해서 구현할 수도 있다.

 

하지만 훨 간단한 방법이 있다.

모든 정점의 자식의 수(혹은 out edge의 개수)를 관리한다.

자식의 수가 0인 정점은 다른 정점으로 이동할 수 없음을 의미하고 이들을 하나씩 제거하면서 부모 정점의 자식의 개수를 줄여준다. 이를 반복하면서 자식의 수가 0이 되는 정점이 없을 때까지 반복하는 것이다.

 

위 그림에서는 우선 7, 8번 정점이 자식의 수가 0이다.

7, 8번 정점을 Queue나 Stack에 추가하고,

Queue나 Stack을 pop한 후 pop된 정점의 부모인 6번 노드의 자식의 개수를 1씩 줄여준다.

pop이 두번 진행 되면 6번 정점의 자식의 개수는 0이 되고, 6번 정점을 Queue나 Stack에 추가한다.

 

위 방식을 계속 하면 된다.

사이클의 일부이거나, 사이클을 자식으로 갖는 정점은 절대 자식의 수가 0이 될 수 없으므로 Queue나 Stack에 추가될 수 없다.

 

코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
parents = [[] for _ in range(n+1)]
child_count = [0] * (n+1)
for _ in range(m):
    a,b = map(int, input().split())
    child_count[a] += 1
    parents[b].append(a)

st = [i for i in range(1, n+1) if child_count[i] == 0]
ans = 0
while st:
    cur = st.pop()
    ans += 1
    for child in parents[cur]:
        child_count[child] -= 1
        if child_count[child] == 0:
            st.append(child)

print(ans)

 

숏코딩

숏코딩도 해보았다.

(n,m),*e=[map(int,i.split())for i in open(0)]
d=[r:=0]*-~n
c=[[]for _ in' '*-~n]
for a,b in e:c[b]+=a,;d[a]+=1
s=[i+1for i in range(n)if d[i+1]<1]
while s:
 i=s.pop();r+=1
 for j in c[i]:
  d[j]-=1
  if d[j]<1:s+=j,
print(r)