[백준]1325 효율적인해킹 #stack

1.풀이

재귀로 풀었을때 시간초과가 발생했다 (소스코드1).

O(NM)이고 제한시간 5초(C++기준) 이므로 살짝 애매한데 최적화가 잘 안된것 같다.

stack으로 풀었고 pypy로 제출하여 정답. (소스코드2)

​

2.소스코드

(1) 소스코드1 (시간초과)

import sys
from collections import deque

N,M=map(int,input().split())
graph={}
for i in range(1,N+1):
    graph[i]=[]
for i in range(M):
    A,B=map(int,sys.stdin.readline().rstrip().split())
    graph[B].append(A)

hackCom=0
ans=[]
for start in range(1,N+1):
    visited=[0 for i in range(N+1)]
    visited[start]=1
    stack = deque([start])
    cnt=1
    while(stack):
        nowNode=stack.pop()
        for toNode in graph[nowNode]:
            if visited[toNode]==0:
                visited[toNode]=1
                cnt+=1
                stack.append(toNode)
    #print(start,cnt)
    if cnt>hackCom:
        hackCom=cnt
        ans=[start]
    elif cnt==hackCom:
        ans.append(start)

print(*ans)

 

(2) 소스코드2 (통과)

import sys
from collections import deque

N,M=map(int,input().split())
graph={}
for i in range(1,N+1):
    graph[i]=[]
for i in range(M):
    A,B=map(int,sys.stdin.readline().rstrip().split())
    graph[B].append(A)

hackCom=0
ans=[]
for start in range(1,N+1):
    visited=[0 for i in range(N+1)]
    visited[start]=1
    stack = deque([start])
    cnt=1
    while(stack):
        nowNode=stack.pop()
        for toNode in graph[nowNode]:
            if visited[toNode]==0:
                visited[toNode]=1
                cnt+=1
                stack.append(toNode)
    #print(start,cnt)
    if cnt>hackCom:
        hackCom=cnt
        ans=[start]
    elif cnt==hackCom:
        ans.append(start)

print(*ans)