1389

날짜 : 2023. 01. 30

사용 언어 : python

 

문제

 

 

코드

import sys

n, m = map(int, sys.stdin.readline().split())  # 노드 개수, 관계 개수
graph = [[int(1e9)] * (n + 1) for i in range(n + 1)]

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

# 그래프 입력
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = 1
    graph[b][a] = 1

# 플로이드 - 워셜 => 모든 경로로 가는 비용 계산
for k in range(1, n + 1):  # 중간노드
    for i in range(1, n + 1): # 시작노드
        for j in range(1, n + 1):  # 도착노드
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])  # 거쳐가는것과 곧바로 가는것 비교
res = list() # 결과
for i in range(1, n + 1):
    temp = 0
    for j in range(1, n + 1):
        temp += graph[i][j]
    res.append(temp)
"""for i in graph:
    print(i)"""
print(res.index(min(res))+1)

 

 

풀이

- 각 노드로 가는 경로에 대해서 입력받은 후 전체 노드에 대해 플로이드-워셜 알고리즘을 활용해 각 노드로 가는 경로의 비용을 구한다.

- 1000^3이고 제한시간이 2초이기 때문에 TLE는 발생하지 않는다.

 

 

알게된 점

- 플로이드-워셜 알고리즘, 다익스트라를 같이 이코테로 10월쯤에 공부했는데 다시 공부하게되었다.

- 확실히 플로이드-워셜은 구현하기 쉬웠지만 다익스트라는 많이 까먹어서 집에 가서 다시 공부해야 할 것 같다.

 

 

 

참고 사이트

-