문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
1325번: 효율적인 해킹 보러 가기
제한시간: 5초
메모리 제한: 256 MB
문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
출력
첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.
예제 입력 1
5 4
3 1
3 2
4 3
5 3
예제 출력 1
1 2
계속 메모리초과를 겪었다...
처음 틀린 코드와 정답 코드를 비교하면
visited를 for문 안에 초기화 해주는 차이가 있다.
문제 자체는 쉽다.
틀린 코드
import sys
from collections import deque
input=sys.stdin.readline
# [[], [3], [3], [4, 5], [], [6], [7], []]
if __name__=="__main__":
N,M=map(int, input().split())
graph=[[] for _ in range(N+1)]
for _ in range(M):
a,b=map(int, input().split())
graph[b].append(a)
visited=[0]*(N+1)
res=[0]*(N+1) # 각 노드별로 몇개와 연결되는지 세주면 된다
Q=deque()
for i in range(1,N+1): # 모든 노드를 확인한다
if visited[i]==0:
Q.append(i)
visited[i]=1 # 중복 방문을 피한다
while Q:
n=Q.popleft()
for e in graph[n]: # 현재 노드랑 연결된 노드를 방문한다
visited[e]=1
res[i]+=1 # 연결될때마다 카운트 증가시켜주면된다
Q.append(e)
max_value=max(res)
for i,v in enumerate(res):
if v==max_value:
print(i, end=' ')
정답도 맞고 새로운 테스트셋을 만들어 확인해도 맞는데 계속해서 메모리 초과를 겪는다.
정답답 코드
import sys
from collections import deque
sys.stdin=open('input.txt','r')
input=sys.stdin.readline
# [[], [3], [3], [4, 5], [], [6], [7], []]
if __name__=="__main__":
N,M=map(int, input().split())
graph=[[] for _ in range(N+1)]
for _ in range(M):
a,b=map(int, input().split())
graph[b].append(a)
res=[0]*(N+1)
for i in range(1,N+1):
Q=deque()
Q.append(i)
visited=[0]*(N+1)
visited[i]=1
res[i]+=1
while Q:
n=Q.popleft()
for e in graph[n]:
if visited[e]==0:
visited[e]=1
res[i]+=1
Q.append(e)
max_value = max(res)
for i,v in enumerate(res):
if v==max_value:
print(i, end=' ')
아쉽다
