파란색가운의 개발 블로그
[이코테] 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. 시작점이 명확하게 존재 -> 다익스트라
모든 경우의 수 구하기 -> 플로이드 워셜 알고리즘
여기 유형은 꽤 쉽기도 하고
기본 코드 암기 이후에 약간의 상황만 바뀌는 느낌이었어서 수월하게 해결할 수 있었다.
이번주는 시간이 남으니까 백준이랑 앞에 빵꾸난 문제들 풀어야겠다 ㅎㅎ
'알고리즘 문제 풀이 > 이코테' 카테고리의 다른 글
[이코테] CH10 그래프 이론 실전문제 2번 팀 결성 (0) | 2024.01.19 |
---|---|
[이코테] CH10 그래프 이론 크루스칼 알고리즘 기본 코드 (0) | 2024.01.19 |
[이코테] CH09 최단경로 실전문제 39번 화성 탐사 (0) | 2024.01.17 |
[이코테] CH09 최단경로 실전문제 38번 정확한 순위 (0) | 2024.01.17 |
[이코테] CH09 최단경로 실전문제 37번 플로이드 (0) | 2024.01.16 |