백준 18651 1865. 웜홀 (Python) 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 벨만 포드 알고리즘을 사용하여 음의 사이클이 존재하는지를 확인하면 된다. 벨만 포드 알고리즘은 링크참고하자. 문제에는 시작 정점이 따로 주어져 있지 않다. 그렇기 때문에 웜홀의 정보를 입력받을 때 도착 지점에 대한 리스트를 Set을 활용하여 저장하였다. 웜홀의 정보를 입력받을 때 S에서 E로 웜홀을 통해서 가면 시간이 줄어들기 때문에 도착 지점인 E가 음의 사이클을 가질 수 있는 후보 지점이라고 생각했다. 이렇게 후보 지점들을 시작 지점으로 설.. 2022. 5. 24. 이전 1 다음
