[백준/Python] 13317 한 번 남았다

📌 문제 탐색하기

• 지구이가 간선의 가중치가 1과 -1만 존재하는 그래프에서 음수 사이클의 존재 여부를 구하는 문제를 풀이함
  • 벨만-포드 알고리즘을 사용했으나, 최단 거리 배열 갱신 과정을 1번 덜 반복해서 (정점 개수 - 2번만 반복) 음수 사이클 존재 여부를 정확히 판별해내지 못함
  • 그러나 채점 결과가 "맞았습니다"여서 틀린 것을 인정하지 않음
• 지구이의 벨만-포드 코드에서 음수 사이클이 없음에도 있다고 판별하는 그래프 예제 만들기
• 정점 개수 N과 간선 개수 M을 출력하고, 두 번째 줄부터 M개의 줄에 시작 정점 s, 끝 정점 e, 가중치 d를 출력하기.
  • 그래프에는 중복 간선이 없어야 함. 
  • 50 ≤ N ≤ 100 / 0 ≤ M ≤ N*(N-1) / 1 ≤ s,e ≤ N / s ≠ e / d = 1 or -1

문제의 조건을 만족하는 그래프는 음수 사이클이 실제로 없어야 하고, 정점 개수 - 2번째 반복에서도 최단 거리가 계속 갱신되는 것처럼 보여야 한다. 즉, 음수 사이클이 없으면서도 최단 거리가 끝까지 갱신될 가능성이 남아있는 상태의 그래프를 만들면 된다.

 

간선의 가중치는 1 또는 -1이어야하므로, -1을 가중치로 갖는 음수 간선을 사용해 최단 거리 값이 계속 줄어드는 경로를 만들면 된다. 정점들이 일직선으로 연결되어 있고, 모든 간선의 가중치가 -1인 그래프를 만들면 된다.

 

또한 지구이의 코드에서 (u, v, D) 간선, 즉 정점 u에서 정점 v로 이어지고, 가중치가 D인 간선에 대하여 d[v]에 min(d[u]+D, d[v])을 대입한다고 했으므로,  마지막 반복 회차까지 최단 거리가 갱신될 수 있도록 간선의 방향과 주어지는 순서에 유의해야 한다.

 

 

📌 정답 코드

print(50, 49)
for i in range(1, 50):
    print(i+1, i, -1)