(python)백준-효율적인 해킹

DongDong·2023년 9월 5일
0

알고리즘 문제풀이

목록 보기
8/20
post-thumbnail
post-custom-banner

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

bfs를 이용해서 푸는 문제였다.
5 4
3 1
3 2
4 3
5 3
입력값이 위와 같이 a,b로 들어올 때 b노드에 a노드가 연결되어있다는 식으로 값을 저장하면 된다.
-> graph[b].append(a)

visited 방문 표시배열은 초기화해줘야 한다!
bfs 함수안에 넣어서 초기화 해주면 된다.

백준에서는 pypy3으만 돌아간당..
input 말고 sys.stdin.readline()쓸것..!

from collections import deque
import sys
n,m=map(int,sys.stdin.readline().split())

graph=[[] for i in range(n+1)]

for i in range(m):
    a,b=map(int,sys.stdin.readline().split())
    graph[b].append(a)

def bfs(graph,start):
    queue=deque([start])
    visited=[False]*(n+1)
    visited[start]=True
    count=1
    while queue:
        v=queue.popleft()
        for i in graph[v]:
            if visited[i]==False:
                visited[i]=True
                queue.append(i)
                count+=1
    return count
answer=[]
for i in range(1,n+1):
    answer.append(bfs(graph,i))
max_v=max(answer)
for i in range(len(answer)):
    if answer[i]==max_v:
        print(i+1,end=' ')
post-custom-banner

0개의 댓글