다음 문제는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾는데
1 ~ n 까지 헛간이 있고 m개의 양방향 통로가 주어졌을 때 1번 헛간에서 술래가 출발한다. 때문에 1번 헛간에서 최단 거리가 가장 긴 헛간을 찾고 헛간이 다수일 때는 가장 작은 번호를 첫번째, 그 때에 1번 헛간부터의 거리, 해당 거리를 가지는 헛간의 개수를 공백을 가지고 출력하면 된다.
import heapq
INF = int(1e9) #최댓값
n, m = map(int, input().split())
graph = [[] * (n + 1) for _ in range(n + 1)]
for i in range(m):
a, b = map(int, input().split())
graph[a].append((b, 1))
graph[b].append((a, 1)) #양 방향이므로 거리를 1로 넣어주기
distance = [INF] * (n + 1)
q = []
distance[1] = 0
heapq.heappush(q, (0, 1)) #거리가 0인 1번 노드부터 시작
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]))
max_distance = 0
result = []
for i in range(1, n + 1):
if max_distance < distance[i]:
max_distance = distance[i]
for i in range(1, n + 1):
if max_distance == distance[i]:
result.append(i)
print(min(result) , max_distance, len(result))
