풀이_1325.md

🦋 백준 1325 - 효율적인 해킹

• Date : 2020.11.9(월)
• Time : 10분

문제

• 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
  
  

코드 풀이

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    adj[y].append(x)

: 단방향 bfs 문제이기 때문에 한쪽 노드에만 자식을 넣어주었다.

for i in range(1,m+1,1):
    visited = [False] * (n + 1)
    need_visit = deque()
    need_visit.append(i)
    while need_visit:
        node = need_visit.popleft()
        if not(visited[node]):
            visited[node] = True
            for j in adj[node]:
                if not visited[j]:
                    need_visit.append(j)
                    count[i] += 1

: bfs문제로 풀었고, 다른점이 있다면 다른 노드로 넘어갈 때 count를 +1 해서 해킹할 수 있는 컴퓨터의 갯수를 추가해주었다. 시간초과 너무 나서 슬펐던 문제.. pypy3로 푸세요..