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

문제

---

1325번: 효율적인 해킹

코드

---

My answer(x)

import sys
from collections import deque
input= sys.stdin.readline

n,m=map(int,input().split())

graph = [set() for i in range(n + 1)]
visited=[0 for i in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    graph[b].add(a)

def dfs(idx):
    visited=[0 for i in range(n+1)]
    visited[idx]=1
    for i in graph[idx]:
           visited[idx]+=dfs(i)
    return visited[idx]

for i in range(1,n+1):
    visited[i]=dfs(i)

max_n=max(visited)

for i in range(n + 1):
    if visited[i] == max_n: print(i, end = ' ')

Another answer

import sys
from collections import deque
input = sys.stdin.readline

def bfs(v):
    queue = deque([v])
    cnt = 1
    visited = [False] * (n+1)
    visited[v] = True
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                cnt += 1
    return cnt

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)

result = []
for i in range(1, n+1):
    result.append(bfs(i))

max = max(result)
for i in range(len(result)):
    if max == result[i]:
        print(i+1, end=' ')

풀이

---

음 우선 결론적으로 나는  이 문제를 못풀었다. 나는 dfs로 접근을 했었는데 시간초과가 떴고 사실 맞는지도 잘 모르겠다.

dfs로 푼 분들도 있는데 대부분 bfs로 푼 것 같다.

우선 이 문제 핵심은 양방향연결이 아니라, 단방향 연결이기 때문에 그래프를 생성할 때 유의해야하며, 반복문을 이용하여 모든 노드를 루트 노드로 놓고 돌려봐야 한다는 것이다. 나도 동일한 방법을 이용해서 dfs로 했는데 왜 시간초과가 날까...맞는지도 모르겠다 ㅠㅠ 예제 결과는 잘 나왔는데 ㅠㅠ 

+) graph를 set으로도 선언해보고, pypy로도 해봤는데 시간초과가 나왔다.. bfs로 풀라고 한다.

+) bfs로 풀어도 시간초과가 나와서 pypy로 제출하니 통과됐다 ㅠㅠ

 

-> 단방향, visited 초기화 만 중요하게 생각하면 될 것 같다.