spfa (4) 썸네일형 리스트형 [ICPC] 백준 3860 - 할로윈 묘지 https://www.acmicpc.net/problem/3860 힌트 더보기 이 문제는 그래프를 제대로 모델링하지 않으면 틀리는 문제다. 다음 요소를 점검해보자. 1. 도착지에서 이동을 불허하는지? 2. 도착 여부보다 음의 사이클 검출 여부가 우선이다. 3. 귀신 구멍에 대한 처리를 제대로 한 게 맞는지? 다음 TC에 대해 답이 Never가 나와야 한다. 확인해보자. 3 3 2 2 1 1 2 1 1 0 1 0 -1 0 0 솔루션 더보기 겉으로 보기엔 벨만포드 알고리즘을 적용하기만 하면 되는 문제로 보인다. 다만 주어진 규칙에 따라 가중치 그래프를 제대로 만들지 않으면 틀린 답을 얻게 된다. 규칙을 다시 정리하면 도착하는 즉시 빠져나와야 하고 귀신 구멍에 들어가면 지정한 위치로 이동하며 묘비로는 갈 수 .. Shortest Path Faster Algorithm(SPFA) 이 게시글에서는 벨만 포드 알고리즘의 평균 시간 복잡도를 크게 개선한 SPFA의 구현법과 특징을 알아본다. SPFA의 사용 의의 SPFA의 시간 복잡도는 벨만 포드와 동일하게 $O(VE)$이지만 SPFA 저격 데이터가 없는 경우 $O(V + E)$의 성능을 낸다고 알려져 있다. 따라서 채점 데이터가 약하다고 추정되는 문제에서 최단 경로를 찾을 때는 SPFA의 사용을 고려할 수 있다. 단, 저격 데이터가 있는 경우 SPFA의 큐 사용에서 발생하는 상수 시간이 더 크기 때문에 벨만 포드보다 느린 퍼포먼스를 보여준다는 것을 유의해야 한다. SPFA는 MCMF의 구현에 많이 이용하므로 플로우와 관련된 알고리즘을 배우기 전에 꼭 숙지해야 하는 알고리즘이다. C++ 구현 SPFA는 큐를 이용해서 BFS와 유사하게 .. [USACO] 백준 6002 - Job Hunt https://www.acmicpc.net/problem/6002 힌트 더보기 어떤 도시를 도착하든 D원을 벌어야 나갈 수 있다. 시작 도시도 예외는 아니다. 풀이 더보기 도시를 잇는 도로와 비행기 노선이 제공될 때 어떻게 하면 큰돈을 벌 수 있을까? 비행기를 타는데 소비되는 비용을 음수 가중치라 생각하면 이 문제는 음수 가중치가 있는 그래프에서 최장 경로를 찾는 문제가 된다. C도 220 이하이므로 벨만포드 알고리즘의 사용을 적극 고려해볼 수 있다. 다만 돈을 버는 행위는 간선이 아닌 정점에서 일어난다는 것에 유의해야 한다. 문제의 상황을 벨만포드로 모델링하기 위해 기존 알고리즘의 구현에서 두 가지 조치를 행하면 된다. 1. 시작점의 초기값을 0이 아닌 D로 둔다. D만큼 벌어야 도시를 나갈 수 있기 .. 백준 1738 - 골목길 icpc.me/1738 문제 분석 가는 길마다 돈을 갈취당하거나 주울 수 있다. 갔던 곳을 또 가도 똑같은 일이 일어난다. 최적의 경로는 보유금을 최대로 한 채로 콘도에 도착하는 경우이며 최적의 경로에 도달할 수 없는 경우가 있다고 한다. 다음을 생각해볼 수 있다. 1. 콘도에 못가는 경우 : 당연하게도 경로 자체가 없으면 콘도에 갈 수 없다. 2. 가는 길에 돈을 얻는 사이클이 있는 경우: 민승이는 최대 보유금을 위해 돈을 줍느라 최대 보유금은 양의 무한대로 발산하므로 콘도에 영영 도착할 수 없게 된다. 이 내용들을 고려하여 금액을 가중치로 바꾸면 음수의 가중치를 처리할 수 있는 알고리즘이 필요하다. 벨만포드/SPFA로 풀어보자. 구현 콘도에 갈 수 없는 경우를 미리 처리해주자 $n \leq 100$ .. 이전 1 다음
