1. 문제 설명 📌

(1) 링크🔗

https://www.acmicpc.net/problem/13317

(2) 해설🕵

지구이의 코드는 벨만포드를 잘못 구현한 코드로서, 정점이 N 개일 떄, N-2번만 완화과정을 거치고, N-1번에서는 음수 사이클 확인을 한다고 한다. 원래라면 N-1번까지 완화 과정을 거치고, N번째에 음수 사이클을 확인한다.
해당 문제의 요구사항은 지구이의 코드가 "틀렸습니다."가 나올 반례 입력을 만드는 것이다.

지구이의 CPP 코드에 대한 분석✨

해당 코드에는 지구이가 만든 틀린 코드와 제대로 돌아가는 벨만포드 코드 2가지로 나뉘고 있다. 여기서 주의해야할 점은 다음과 같다.

1️⃣ 시작점에서 정점까지의 최단거리를 나타내는 dis[] 배열이 0으로 초기화 되고 있다.
2️⃣ 입력을 받은 순서대로 완화과정을 거친다.

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: BELLMAN_FORD ALGORITHM 바로 알기

지구이의 코드가 "틀렸습니다."가 나오려면, (1) N-1번까지 실질적인 완화과정이 진행되야하고, (2) 음수 사이클이 없어야 한다.
만약 N-2번의 반복 내에서 완화과정이 끝나버린다면, 지구이의 코드가 진행하는 N-1번에서 음수 사이클 여부를 확인하는 게 효과가 있다. 완화과정을 다 마치고도 최단거리 배열이 줄어드는 것이기 때문이다. 이러면 올바른 벨만포드 코드와도 반환값이 같아진다.
또한 음수 사이클이 존재한다면, 지구이 코드처럼 N-1에서 음수사이클 여부를 확인하든, 올바른 코드처럼 N번에서 확인하든 둘 다 최단 거리 배열의 값은 바뀐다. 따라서, 지구이의 코드가 올바른지 아닌지를 확인할 수 없다.

여기까지만 생각하고 코드를 짜면 50%에서 틀릴 수 있다. 왜냐하면 지구이가 짠 CPP 코드에 복병이 숨어있기 때문이다.
먼저 해설에서 설명한대로, 최단 거리 배열인 dis[]가 모두 0으로 초기화 되어 있다. 따라서 가중치로 1을 넣는다면, 아무리 완화 과정을 거쳐도 갱신되지 않는다.
또한, 입력 받은 순서대로 완화를 진행한다. 따라서 출발점인 1부터 오름차순으로 입력을 주면 한 번의 완화 과정에 최단 거리 배열이 완성된다. 이 떄문에, 한 번에 하나씩 N-1까지 최단거리 갱신이 점진적으로 이뤄지게 하고 싶다면 내림 차순으로 입력을 줘야 한다.

(2) SUDO CODE 📜

0️⃣ 정점의 개수가 50이고 간선의 가중치가 49개, 모든 가중치가 -1인 일자형 트리 형태의 그래프 입력을 출력한다.

(3) 시간복잡도 분석 🕓

시간 복잡도가 필요 없는 문제이다.

3. 구현 코드 🔎

public class Main {
    public static void main(String[] args) {
        System.out.println(50 + " " + 49);
        for (int i = 49; i > 0; i--) {
            System.out.println(i +" "+ (i+1)+" "+ -1);
        }
    }
}

4. 배운 것들 🎯

벨만 포드에 대해 더 깊게 생각하는 계기가 된 것 같다. 나는 '무조건 한번의 완화과정에 하나의 정점으로 가는 최단 거리는 갱신된다!' 라고 생각했는데, 이는 틀린 생각이었다. 입력으로 들어가는 간선 리스트의 순서에 따라 완화가 N-1 내에 언제 마무리 될지는 달라진다. 확실한 것은 N-1내에는 완성이 된다는 것이다.