[백준 파이썬] 1325 효율적인 해킹

[백준 파이썬] 1325 효율적인 해킹

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

1325번: 효율적인 해킹

 

문제

이 회사는 n개의 컴퓨터로 이루어져 있다

해커는 귀찮아서 한 번의 해킹으로 여러 개의 컴퓨터를 해킹하려고 한다

이 회사의 컴퓨터는 신뢰의 관계와 신뢰하지 않는 관계로 이루어져 있는데

A과 B를 신뢰하는 경우 B를 해킹하면 A도 해킹할 수 있다 

신뢰관계가 주어졌을대 한 번에 가장 많이 해킹할 수 있는 컴퓨터 번호를 출력하는 프로 그래을 작성 하시오

반응형

입력

첫 줄에 n, m이 주어지면 n은 컴퓨터의 수이며 다음줄부터 

m 줄은 신뢰하는 관계 AB와 같은 형식으로 주어진다 

출력

한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이

처음 문제를 풀었을 때에는 DFS를 이용하였지만 python3와 pypy3 모두 다 시간초과 또는 메모리초과가 나와서

BFS로 풀었다 

BFS에 최대 컴퓨터 연결수를 알 수 있는 코드를 추가해야 한다 

BFS를 컴퓨터 수만큼 반복해야 한다 

 

BFS를 반복하면서 연결된 컴퓨터수의 최댓값인지 아닌지 판단해야 하면

최댓값이면 새로운 리스트를 만들어 집어넣고 값이 같으면 현재 리스트에 집어넣는 방식으로 최대 연결수를 가지는 컴퓨터 번호를 찾을 수 있다 

코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x,visted):
    cnt=1 #최대컴퓨터수를 알수는 변수
    q=deque([x])
    visted[x]=True
    while q:
        point=q.popleft()

        for i in graph[point]:
            if not visted[i]:
                visted[i]=True
                cnt+=1
                q.append(i)
    return cnt



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


data=[]
for i in range(1,n+1):
    v = [False] * (n + 1)
    max_data=bfs(i,v)
    if value<max_data:
        value=max_data
        data=[]
        data.append(i)
    elif value==max_data:
        data.append(i)




print(*data)

결과

DFS로 풀어볼려고 이것저것 시도 해보았지만 시간초과나 나온다.