[bfs/백준] 1325번 : 효율적인 해킹

- 문제 : https://www.acmicpc.net/problem/1325

첫 번째 풀었을 때는 정답보고 30회 가량 시도했는데도 계속 안됐던 것 같은데 

이번엔 비교적 쉽게 푼 느낌이다 

 

자식노드를 중심으로 진행하고, 하나의 노드마다 방문한 노드 수를 리스트 인덱스에 저장한 뒤, 그 중에 최댓값을 가진 인덱스들을 오름차순으로 출력하는 걸로 이해했다 

visit 인덱스마다 진행한 깊이를 진행하려고했는데, 이렇게 하니까 메모리 초과가 발생했다 

그래서 풀이를 봤더니 visit는 매 노드마다 초기화하고, 다른 리스트에 각 노드의 깊이를 저장해서 진행하는 것 같아서 

그렇게 변형했더니 정답이 떴다 

시간이 꽤 오래걸렸던 문제다 

 

- 정답 풀이 : 

from collections import deque

n,m=map(int,input().split())
data=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    data[b].append(a)

def bfs(v):
    visit=[0]*(n+1)
    visit[v]=1
    queue=deque()
    queue.append(v)
    while queue:
        x=queue.popleft()
        for i in data[x]:
            if not visit[i]:
                visit[i]=1
                count[v]+=1
                queue.append(i)                   

count=[0]*(n+1)
result=0
for i in range(1,n+1):
    bfs(i)
    result=max(result,max(count))
    
for i in range(1,n+1):
    if count[i]==result:
        print(i, end = ' ')

 

 

 

 

- 이렇게 풀면 메모리 초과난다(방문한 노드 처리 안 해줘서)

from collections import deque

n,m=map(int,input().split())
data=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    data[b].append(a)

def bfs(v):
    visit[v]=1
    queue=deque()
    queue.append(v)
    while queue:
        x=queue.popleft()
        if len(data[v])!=0:
            for i in data[x]:
                visit[v]+=1
                queue.append(i)                   

visit=[0]*(n+1)
answer=''
result=0
for i in range(1,n+1):
    bfs(i)
    result=max(result,visit)
    
for i in range(1,n+1):
    if visit[i]==result:
        print(i, end = ' ')