Q40. 숨바꼭질
🐣문제
동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1~N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다.
동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요.
입력 조건
첫째 줄에는 N과 M이 주어지며 공백으로 구분합니다. (2<=N<=20000, 1<=M<=50000)
이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다.입력 예시
6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2
출력 조건
첫번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러 개면 가장 작은 헛간 번호),
두번째는 그 헛간까지의 거리를,
세번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력합니다.출력 예시
4 2 3
🐥풀이
1번 헛간에서 숨바꼭질을 시작하므로, 출발점을 1번 헛간으로 두고 나머지 헛간까지의 거리를 다익스트라를 활용하여 거리 테이블을 업데이트 한다.
다익스트라 실행 후, 가장 먼 헛간에 숨어야 하므로 거리 테이블에서 가장 먼 최단거리를 구한다. 구한 후, 해당 헛간 번호, 구한 최단 거리, 거리 테이블에서의 구한 최단 거리의 개수를 구해 출력한다.
🐓코드
import heapq
# 입력값
n, m = map(int, input().split()) # 헛간개수, 통로개수
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
# 양방향 통로
graph[a].append(b)
graph[b].append(a)
# 거리 테이블 초기화
distance = [int(1e9)]*(n+1)
# 다익스트라 시작
q = []
distance[1] = 0 # 술래는 1번 헛간에서 시작
heapq.heappush(q,(0,1)) # 최단경로, 헛간번호
while q:
cost, num = heapq.heappop(q) # 거리, 헛간번호
if distance[num]<cost:
continue
# >
for g in graph[num]:
if distance[g] > cost+1:
distance[g] = cost+1 # 새로 이동하므로 +1
heapq.heappush(q, (cost+1, g))
dist = max(distance[1:]) # 최단경로 최댓값 (1번 헛간 ~ N번 헛간 중)
# 헛간번호, 최단거리, 같은 최단거리의 헛간 개수
print(distance.index(dist), dist, distance.count(dist))⭐2022.05.11
스터디 당시, 반복적으로 다익스트라를 써오면서 익숙해진 채로 풀었던 문제여서 나름 수월하게 풀어냈던 것 같다!
