FilesExpand file tree

master

/

4.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (52 loc) · 2.14 KB

master

/

4.py

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (52 loc) · 2.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

56

57

58

59

import heapq

import sys

input = sys.stdin.readline

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기

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

# 시작 노드를 1번 헛간으로 설정

start = 1

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기

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

# 최단 거리 테이블을 모두 무한으로 초기화

distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기

for _ in range(m):

a, b = map(int, input().split())

# a번 노드와 b번 노드의 이동 비용이 1이라는 의미(양방향)

graph[a].append((b, 1))

graph[b].append((a, 1))

def dijkstra(start):

q = []

# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입

heapq.heappush(q, (0, start))

distance[start] = 0

while q: # 큐가 비어있지 않다면

# 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기

dist, now = heapq.heappop(q)

# 현재 노드가 이미 처리된 적이 있는 노드라면 무시

if distance[now] < dist:

continue

# 현재 노드와 연결된 다른 인접한 노드들을 확인

for i in graph[now]:

cost = dist + i[1]

# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우

if cost < distance[i[0]]:

distance[i[0]] = cost

heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행

dijkstra(start)

# 가장 최단 거리가 먼 노드 번호(동빈이가 숨을 헛간의 번호)

max_node = 0

# 도달할 수 있는 노드 중에서, 가장 최단 거리가 먼 노드와의 최단 거리

max_distance = 0

# 가장 최단 거리가 먼 노드와의 최단 거리와 동일한 최단 거리를 가지는 노드들의 리스트

result = []

for i in range(1, n + 1):

if max_distance < distance[i]:

max_node = i

max_distance = distance[i]

result = [max_node]

elif max_distance == distance[i]:

result.append(i)

print(max_node, max_distance, len(result))