백준 13317 한 번 남았다

🔗 백준 13317 한 번 남았다 

Python

📌오늘의 학습 키워드

• 벨만 포드 

✨공부한 내용 본인의 언어로 정리하기

• 벨민 포드는 방향이 있는 그래프에서 각 노드 사이의 최단 거리를 구하는 방법이다.

📚오늘의 회고

• 첫번째에서는 그래서 뭘 하라는 건데? 라는 의문을 가졌다가 아 테스트케이스를 제시하라는 거구나 알았다.
• 근데 내가 바로 Dijkstra 알고리즘밖에 모르는 지구이여서 문제였다. 😅
• 중요한 조건으로는
  1. 간선은 1 또는 -1 의 가중치만 갖는 다는 것
  2. 지구이는 정점의 갯수 - 2 번까지는 제대로 수행하므로 정점의 갯수 - 1 번째에도 변화가 있어야 할 것
• 막 복잡하게 해보다가 구글링해본 결과 답은 일 차 트리였는데, 간선을 1->2, 2->3 순으로 적지 말고 49->50, 48->49 이렇게 적어야 2번째 중요 조건을 만족했다.

[🤓문제 해결 코드]

 

print(50, 49)

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