[USACO] 숨바꼭질

USACO 숨바꼭질

다익스트라 / 최단거리

 

 

[문제]

 

 

특정한 번호(1번)에서 다른 경로까지의 최단거리를 찾는 문제이므로 플로이드 보다는 다익스트라 알고리즘이 적합함.

중요한 부분은 하나의 통로가 서로 다른 두 헛간을 연결하는 쌍방의 통로라는 것!

최단거리가 가장 먼 헛간을 찾아야 하며 최단거리의 의미는 지나야 하는 길의 최소 개수이므로 거리비용은 1로 설정하면 됨

 

 

 

[과정]

 

• 하나의 노드에서 연결되는 헛간 정보를 반대편 노드에서도 연결해주기    # 첫번째 반복문
• 다익스트라 수행
• 0번째 인덱스를 제외한 distance에서 가장 큰값을 갖는 인덱스를 찾아 해당 번호 출력     # 숨어야하는 헛간 번호
• 헛간번호를 index로 가지는 distance의 값 출력     # 헛간 까지의 거리
• count함수를 사용하여 숨어야 하는 헛간과 같은 거리의 헛간의 수를 출력

 

 

 

[소스코드]

 

# 숨바꼭질
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

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

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

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

def dijkstra(start):
    q = []
    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(1)

result = []
cnt = distance.index(max(distance[1:]))
result.append(cnt)    # 숨어야하는 헛간 번호
result.append(distance[cnt])     # 헛간 까지의 거리 
result.append(distance.count(distance[cnt]))     # 헛간과 같은 거리를 갖는 헛간의 개수
result = ' '.join(map(str, result))
print(result)

 

 

---

 

[통과]