본 글은 작성자가 직접 푼 코드를 바탕으로 Chat-GPT를 활용하여 포스팅한 글입니다.
https://www.acmicpc.net/problem/1325
문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
문제 이해
주어진 문제에서는 컴퓨터들 간의 신뢰하는 관계가 주어지고, 한 번의 해킹으로 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 찾아야 한다.
입력
- 정수 n, m (1 ≤ n ≤ 10,000, 1 ≤ m ≤ 100,000)
- m개의 줄에는 각각 신뢰 관계를 나타내는 정수 a, b (1 ≤ a, b ≤ n)
출력
- 한 번의 해킹으로 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호
해결 방법
주어진 문제를 해결하기 위해서는 다음과 같은 방법을 사용할 수 있다.
- 신뢰 관계를 나타내는 그래프를 생성한다.
- 각 컴퓨터를 시작점으로 BFS를 수행하여 해킹할 수 있는 컴퓨터의 수를 계산한다.
- 계산된 수 중 가장 큰 값을 찾는다.
- 가장 큰 값과 일치하는 컴퓨터의 번호를 출력한다.
주어진 코드에서는 입력으로 주어진 신뢰 관계를 그래프로 표현하고, 각 컴퓨터를 시작점으로 BFS를 수행하여 해킹할 수 있는 컴퓨터의 수를 계산하고, 가장 큰 값을 찾아 해당 컴퓨터의 번호를 출력하는 로직을 포함하고 있다.
- 입력으로 주어진 신뢰 관계를 그래프로 표현한다.
- 각 컴퓨터를 시작점으로 BFS를 수행하여 해킹할 수 있는 컴퓨터의 수를 계산한다.
- 계산된 수 중 가장 큰 값을 찾는다.
- 가장 큰 값과 일치하는 컴퓨터의 번호를 출력한다.
전체 코드
from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
com = [[] for _ in range(n+1)]
for _ in range(m):
b, a = map(int, input().split(" "))
com[a].append(b)
def bfs(i):
q = deque([i])
visitied = [False for _ in range(n+1)]
visitied[i] = True
cnt = 0
while q:
num = q.popleft()
for nx in com[num]:
if not visitied[nx]:
cnt += 1
visitied[nx] = True
q.append(nx)
return cnt
answer = []
pr = []
for i in range(1,n+1):
tmp = bfs(i)
answer.append(tmp)
M = max(answer)
for j in range(len(answer)):
if answer[j] == M:
pr.append(j+1)
print(*pr)본 코드는 pypy3 출제 형식으로 할 때만 통과처리가 된다.
NLP Engineer