본문 바로가기
Algorithm/백준

[Python] 백준 1325번 - 효율적인 해킹 (실버 1)

by 애기 개발자 2023. 9. 21.
반응형

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

 

1325번: 효율적인 해킹

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한

www.acmicpc.net

 

혼자 힘으로 풀었는가? x

알고리즘 분류
 - DFS
 - BFS

 

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 


 

BFS/DFS로 풀면되겠네 쉽네

 

하고 풀러 들어가면 '시간초과' 를 보게 된다.

 

시간초과 코드

더보기
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
data = [ [0]for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
data[b].append(a)
cnt = [0] * (n+1)
from collections import deque
def bfs(n):
q = deque()
q.append(n)
visited[n] = 1
cnt = 0
while q:
now = q.popleft()
size = len(data[now])
if size != 0:
cnt += size-1
for i in range(1, size):
if visited[data[now][i]] == 0:
q.append(data[now][i])
visited[now] = 1
return cnt
for i in range(1, n+1):
visited = [0] * (n+1)
cnt[i] = bfs(i)
k = max(cnt)
for i in range(1, n+1):
if k == cnt[i]:
print(i, end=' ')

 

정답 코드 (PyPy3 제출)

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
data = [ [] for _ in range(n+1)]
cnt = [0] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
data[b].append(a)
from collections import deque
def bfs(n):
q = deque()
q.append(n)
visited[n] = 1
while q:
now = q.popleft()
cnt[n] += 1
for i in data[now]:
if visited[i] == 0:
visited[i] = 1
q.append(i)
result = -1
resultList = []
for i in range(1, n+1):
visited = [0] * (n+1)
bfs(i)
if cnt[i] > result:
resultList = []
result = cnt[i]
resultList.append(i)
elif cnt[i] == result:
resultList.append(i)
for i in resultList:
print(i, end=' ')

솔직히.. 큰 차이는 없어 보이는데... 

 

최대 값을 찾는 과정에서 배열에 계속 쌓아서 다시 찾는 것과 초기화하며 최대 값만 넣는 것의 차이라고 볼 수 있다.  

반응형

댓글