[백준] [BFS] 1325.효율적인 해킹

1325.효율적인 해킹

1325번: 효율적인 해킹

 

• 내 첫 풀이
  • union-find라고 생각했지만 이렇게 하면 
  • 각 노드가 몇개씩 연결되었는지 알 수 없음
  • 부모노드의 자식개수만 알 수 있는것

#1325 효율적인 해킹
#한번의 해킹으로 여러개 컴퓨터 해킹
#r:한번에 가장 많은 컴퓨터를 해킹할수있는 컴퓨터 번호


def union(x,y):
    xroot=find(x)
    yroot=find(y)
    if xroot>yroot: #작은쪽으로
        root[xroot]=yroot 
    else:
        root[yroot]=xroot

def find(x):
    if root[x]!=x:
        root[x]=root[root[x]]
    return root[x]
    
#n개의 컴퓨터, 신뢰관계 m
n,m=map(int,input().split())
computer=[[0 for _ in range(n+1)] for _ in range(n+1)]


maxCnt=0
result=[]
root=[i for i in range(n+1)]


for _ in range(m):
    a,b=map(int,input().split())
    computer[a]=b
    computer[b]=a
    union(a,b)

print(root)
for i in range(1,n+1):
  cnt=root.count(find(i))
  if maxCnt>cnt:
    continue
  elif maxCnt<cnt:
    maxCnt=cnt
    result.clear()
  result.append #같을때는 추가만

print(result)

 

• 다시 풀기

#1325 효율적인 해킹
#한번의 해킹으로 여러개 컴퓨터 해킹
#r:한번에 가장 많은 컴퓨터를 해킹할수있는 컴퓨터 번호
from collections import deque
  
#n개의 컴퓨터, 신뢰관계 m
n,m=map(int,input().split())
computer=[[0 for _ in range(n+1)] for _ in range(n+1)]

maxCnt=0
result=[]
queue=deque()
visited=[0 for _ in range(n+1)]
lst=[]

for _ in range(m):
    a,b=map(int,input().split())
    #b를 해킹할때 a가 가능
    computer[b]=a
      
#연결된 노드 수 세고싶으니까 큐
def bfs(start):
  queue.append(start)

  while queue:
    q=queue.popleft()

    #처음 for문: 방문되지 않은 자식들 수를 더하고
    for com in computer[q]:
        visited[q]+=1
        queue.append(q)
        for c in com:
            if visited[c]!=0:
                continue
            visited[q]+=1

 
        


for i in range(1,n+1):
  cnt=root.count(find(i))
  if maxCnt>cnt:
    continue
  elif maxCnt<cnt:
    maxCnt=cnt
    result.clear()
  result.append #같을때는 추가만

print(result)

 

• 세번째 풀이

#1325 효율적인 해킹
#한번의 해킹으로 여러개 컴퓨터 해킹
#A-> B: B해킹 -> A해킹 가능
#r:한번에 가장 많은 컴퓨터를 해킹할수있는 컴퓨터 번호
from collections import deque
from collections import defaultdict
  
#n개의 컴퓨터, 신뢰관계 m
n,m=map(int,input().split())
computer=[]

maxCnt=0
result=[]
queue=deque()


visited=defaultdict(list)
cnt=defaultdict(int)
for _ in range(m):
    a,b=map(int,input().split())
    #b를 해킹할때 a가 가능
    computer[a]=b
    computer[b]=a
  
      
#연결된 노드 수 세고싶으니까 큐
def bfs(start):
    queue.append(start)
  
    while queue:
        q=queue.popleft()
        visited[q].append(q)
    
        for com in computer[q]:
            if com not in visited[q]:
                visited[q].append(com) #방문처리
                cnt[q]+=1
                for c in com:
                    if c not in visited[q]:
                        visited[q].append(c)
                        cnt[q]+=1
           #자식노드만 먼저 세야하는거 아니므로
            queue.append(com)
          
bfs(1)
print(visited)

 

• 다른 사람 풀이
  • BFS+for문을 이용하여 풀 수 있는데, 매 순회마다 visited를 초기화시켜야 하는 것에 주의해야 한다
  • -> bfs함수 실행시마다 초기화
  • print(*리스트) : 리스트에 있는 값을 한칸씩 띄어서 출력해준다

#1325 효율적인 해킹
#한번의 해킹으로 여러개 컴퓨터 해킹
#A-> B: B해킹 -> A해킹 가능
#r:한번에 가장 많은 컴퓨터를 해킹할수있는 컴퓨터 번호
import sys
input=sys.stdin.readline

from collections import deque
from collections import defaultdict
  
#n개의 컴퓨터, 신뢰관계 m
n,m=map(int,input().split())
computer=defaultdict(list)

maxCnt=0
result=[]
queue=deque()

for _ in range(m):
    a,b=map(int,input().split())
    #b를 해킹할때 a가 가능 : 해킹 방향 한쪽으로만 추가하면됨
    computer[b].append(a)
  
      
#연결된 노드 수 세고싶으니까 큐
def bfs(start):
    #각 번호마다 bfs를 돌기때문에
    #자식의 자식까지 전부 다 도는 횟수를 하나의 cnt로 계산
    cnt=1
    #visited는 매번 초기화해주기
    visited=[]

    queue.append(start)
    visited.append(start)

    #연결된 노드들 모두 세기
    while queue:
        q=queue.popleft()
        for com in computer[q]:
            if com not in visited:
                visited.append(com)
                cnt+=1
                queue.append(com)

    return cnt

for i in range(1, n+1):
    c=bfs(i)
    if maxCnt>c:
        continue
    elif maxCnt<c:
        maxCnt=c
        result.clear()
    result.append(i)
      
print(*result)