1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/13317(2) 해설🕵지구이의 코드는 벨만포드를 잘못 구현한 코드로서, 정점이 N 개일 떄, N-2번만 완화과정을 거치고, N-1번에서는 음수 사이클 확인을 한다고 한다. 원래라면 N-1번까지 완화 과정을 거치고, N번째에 음수 사이클을 확인한다.해당 문제의 요구사항은 지구이의 코드가 "틀렸습니다."가 나올 반례 입력을 만드는 것이다.지구이의 CPP 코드에 대한 분석✨해당 코드에는 지구이가 만든 틀린 코드와 제대로 돌아가는 벨만포드 코드 2가지로 나뉘고 있다. 여기서 주의해야할 점은 다음과 같다.1️⃣ 시작점에서 정점까지의 최단거리를 나타내는 dis[] 배열이 0으로 초기화 되고 있다.2️⃣ 입력을 받은 순서대로..

1. 벨만포드 알고리즘이란?음수인 가중치가 존재하는 그래프에서도 최단 경로를 구할 수 있게 해주는 알고리즘.1️⃣ ONE TO ALL 알고리즘: 시작점을 고르면, 해당 정점에서 모든 정점까지의 최단 경로를 구할 수 있다.2️⃣ 음수 가중치가 있어도 괜찮아: 다익스트라는 안되지?3️⃣ 음수 사이클이 존재하는지도 확인 가능: 음수 사이클이 존재한다면, 사실 하나 이상의 정점으로의 최단 경로가 $- \infty $가 되기 때문에, 최단경로를 구하는 게 무의미해짐. 따라서 최단 경로를 구하는 게 무의미한지 여부도 파악 가능!음수 사이클가중치 그래프에서 정점 A에서 시작해서 A로 돌아왔는데 가중치의 합이 음수인 경우, 해당 사이클을 음수 사이클이라고 한다.해당 예시에서는 사이클을 돌수록 출발지에서 A,B,C까지의..