[최단경로] 숨바꼭질

[ericagong]

⭐ 성찰

1. 각 헛간 간의 거리가 1로 고정되어 있다는 점에서 굳이 다익스트라/FW를 쓰지 않고 BFS로도 풀이 가능

❓ 문제 상황

[숨바꼭질](이코테 p.390)

👨‍💻 문제 해결: 다익스트라를 통한 최단 경로

✅ 1차 풀이: 다익스트라 알고리즘(25min)

1. input 받을 때, 양방향 그래프임을 고려
2. 다익스트라 통해 최단경로 도출
3. 다익스트라 결과물에 대해 최장 경로를 가진 노드 리스트를 찾는 find 함수 생성

   
   import sys
   from heapq import heappush, heappop

input = sys.stdin.readline INF = int(2e9)

n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] d = [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): hq = [] d[start] = 0 heappush(hq, (d[start], start)) while hq: cd, cn = heappop(hq) if d[cn] < cd: continue for item in graph[cn]: node, edge = item new_cost = cd + edge if new_cost < d[node]: d[node] = new_cost heappush(hq, (d[node], node))

def find(): max_d = -INF cand = [] for i, cd in enumerate(d): if i == 0: continue if max_d < cd: max_d = cd cand = [] cand.append(i) elif max_d == cd: cand.append(i) print(cand[0], max_d, len(cand))

dijkstra(1) find()