[백준 13317] 한 번 남았다 (C#, C++) - soo:bak

문제 링크

13317번 - 한 번 남았다

설명

벨만-포드 알고리듬의 잘못된 구현을 찾는 상황에서, 정점 N개와 간선 M개로 구성된 그래프를 출력할 때, N-2번만 반복한 후 음수 사이클을 검사하는 잘못된 구현이 오답을 내도록 하는 반례 그래프를 구성하는 문제입니다.

벨만-포드 알고리듬은 정점이 N개일 때 N-1번 반복해야 모든 최단 경로를 제대로 계산할 수 있습니다. N-2번만 반복하면 길이가 N-1인 최단 경로를 완전히 계산하지 못하므로, 이를 이용하여 반례를 만들 수 있습니다.

접근법

1번부터 50번까지 일렬로 연결된 단방향 체인 그래프를 만듭니다. 각 간선의 가중치는 -1로 설정하여 음수 간선이지만 사이클은 없는 구조를 만듭니다.

이 그래프에서 1번 정점부터 50번 정점까지의 최단 경로는 49개의 간선을 거쳐야 합니다. 따라서 N-2번만 반복하면 마지막 정점까지 거리가 완전히 갱신되지 않습니다. N-2번 반복 후 한 번 더 모든 간선을 확인하면 거리가 갱신되므로, 잘못된 구현은 이를 음수 사이클로 오판하게 됩니다.

N=50, M=49로 설정하고, 1→2, 2→3, …, 49→50 형태의 간선을 역순으로 출력하면 조건을 만족합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      Console.WriteLine("50 49");
      for (var i = 49; i > 0; i--)
        Console.WriteLine($"{i} {i + 1} -1");
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cout << 50 << " " << 49 << "\n";
  for (int i = 49; i > 0; i--)
    cout << i << " " << i + 1 << " " << -1 << "\n";
  
  return 0;
}