iwtkmn   1년 전

벨만-포드 알고리즘은 한 점에서 다른 점 까지 최소 거리를 구하는 알고리즘이지만 해당 문제에서 원하는 것은 최소 거리가 아니라 음의 사이클이 존재하는 지에 대한 내용입니다. 따라서 벨만-포드 알고리즘에서 확인하는 "출발하고자 하는 정점이 한번이라도 갱신 되었는가?" 조건은 필요가 없습니다. 이를 확인한다면 모든 정점에서 출발하는 경우를 당연히 세야 하기에 TLE가 발생할 수 밖에 없습니다. 

대신 갱신 여부를 파악하지 않고 벨만-포드 알고리즘을 돌리면 "음의 사이클이 존재하는가"는 판별할 수 있습니다.. 

틀렸습니다-시간초과 나서 다른 분들 질문 글 보다가 저랑 다른 부분이 있길래 고민하다가 알게 되었습니다.. 다른 분들은 너무 오랜 시간 쓰지 않으셨으면 좋겠습니다..

댓글을 작성하려면 로그인해야 합니다.