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

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: 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=' ')

 

---

아쉽다