[이코테] CH09 최단경로 실전문제 40번 숨바꼭질

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def findMax(start):
    q = []
    heapq.heappush(q,(0,start)) 
    distance[start] = 0
    while q:
        dist,now = heapq.heappop(q) # now는 노드 번호고 dist는 비용
        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]))



N,M = map(int,sys.stdin.readline().split())
graph = [[] *(N+1) for _ in range(N+1)] # 얘를 INF로 초기화하면 안되는구나...
for _ in range(M):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append((b,1))
    graph[b].append((a,1))
distance = [INF] *(N+1)
findMax(1)
maxValue = 0
index = 0
for i in range(N,0,-1):
    if distance[i] >= maxValue:
        maxValue = distance[i]
        index = i
print(index,maxValue,distance.count(maxValue))

최단경로 문제 유형을 마무리하면서!

 

1. 다익스트라 vs 플로이드 워셜 알고리즘인지 판단

N의 크기나 시간 제한 한번 보고 판단하기.

2. 시작점이 명확하게 존재 -> 다익스트라

모든 경우의 수 구하기 -> 플로이드 워셜 알고리즘

여기 유형은 꽤 쉽기도 하고 

기본 코드 암기 이후에 약간의 상황만 바뀌는 느낌이었어서 수월하게 해결할 수 있었다.

이번주는 시간이 남으니까 백준이랑 앞에 빵꾸난 문제들 풀어야겠다 ㅎㅎ