2019.03.16) 백준 최단경로 특집 5편 - 10159(PyPy3)

2019. 3. 16. 23:07프로그래밍(주력)/백준 문제풀이

최적화를 안하는것 같지만 한거다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from heapq import heappush, heappop
 
INF = 1e9
 
= int(input())
= int(input())
 
# 작은쪽 저장
graph1 = {i: list() for i in range(1, N + 1)}
# 큰쪽 저장
graph2 = {i: list() for i in range(1, N + 1)}
 
for _ in range(M):
    a, b = map(int, input().split(' '))
    graph1[a].append(b)
    graph2[b].append(a)
 
 
def search(p0):
    hq = list()
    visited = {i: False for i in range(1, N + 1)}
    heappush(hq, p0)
    # 작은쪽 쭉 탐색
    while hq:
        now = heappop(hq)
        if visited[now]:
            continue
        visited[now] = True
        for nxt in graph1[now]:
            if not visited[nxt]:
                heappush(hq, nxt)
 
    heappush(hq, p0)
    visited[p0] = False
    # 큰쪽 쭉 탐색
    while hq:
        now = heappop(hq)
        if visited[now]:
            continue
        visited[now] = True
        for nxt in graph2[now]:
            if not visited[nxt]:
                heappush(hq, nxt)
    re = 0
    # 방문을 못했으면 카운팅
    for i in range(1, N + 1):
        if not visited[i]:
            re += 1
 
    return re
 
 
for i in range(1, N + 1):
    print(search(i))
 
cs