BOJ 1865 웜홀 (음수 사이클 판별 - 플로이드 워셜, 벨만 포드 2개 풀이)
그래프 내에 음수 사이클이 존재하는지 판별하는 문제. 시간이 뒤로 가기 위해서는 경로의 가중치 합이 음수가 되어야 하며, 출발지로 돌아왔을 때 음수라면 그 경로 상에 음수 사이클이 있음을 의미함.
BOJ
Page 3 of 6
BOJ 1956 운동 (FloydWarshall 이용 최단 사이클 구하기)
방향 그래프에서 가장 짧은 길이의 '사이클(Cycle)' 구하기. (사이클이 없으면 -1 출력)
BOJ 1647 도시 분할 계획
$N$개의 집과 $M$개의 도로가 주어졌을 때, 마을을 두 개의 분리된 컴포넌트로 분할하며 도로 유지비의 합을 최소화하는 문제입니다. 각 마을 내부의 집들은 서로 연결되어 있어야 한다는 점이 핵심입니다.
BOJ 1922 네트워크 연결 (MST, UnionFind)
모든 컴퓨터(노드)를 연결하되, 연결 비용의 총합을 최소일때 연결비용 구하기.
BOJ 11779 최소비용 구하기 2 (dijkstra)
시작점에서 도착점까지 가는 최소 비용을 출력하고, 최단 경로에 포함된 도시의 개수와 그 경로를 순서대로 출력해야 함.
BOJ 15663 N과 M (9)
중복된 숫자가 포함된 $N$개의 수에서 $M$개를 고른 수열을 중복 없이 사전 순으로 출력하기.