벨만포드 (3) 썸네일형 리스트형 [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 솔루션 더보기 겉으로 보기엔 벨만포드 알고리즘을 적용하기만 하면 되는 문제로 보인다. 다만 주어진 규칙에 따라 가중치 그래프를 제대로 만들지 않으면 틀린 답을 얻게 된다. 규칙을 다시 정리하면 도착하는 즉시 빠져나와야 하고 귀신 구멍에 들어가면 지정한 위치로 이동하며 묘비로는 갈 수 .. 백준 1738 - 골목길 icpc.me/1738 문제 분석 가는 길마다 돈을 갈취당하거나 주울 수 있다. 갔던 곳을 또 가도 똑같은 일이 일어난다. 최적의 경로는 보유금을 최대로 한 채로 콘도에 도착하는 경우이며 최적의 경로에 도달할 수 없는 경우가 있다고 한다. 다음을 생각해볼 수 있다. 1. 콘도에 못가는 경우 : 당연하게도 경로 자체가 없으면 콘도에 갈 수 없다. 2. 가는 길에 돈을 얻는 사이클이 있는 경우: 민승이는 최대 보유금을 위해 돈을 줍느라 최대 보유금은 양의 무한대로 발산하므로 콘도에 영영 도착할 수 없게 된다. 이 내용들을 고려하여 금액을 가중치로 바꾸면 음수의 가중치를 처리할 수 있는 알고리즘이 필요하다. 벨만포드/SPFA로 풀어보자. 구현 콘도에 갈 수 없는 경우를 미리 처리해주자 $n \leq 100$ .. 백준 - 1219 : 오민식의 고민 https://www.acmicpc.net/problem/1219 문제의 맥락을 보면 최단 경로 알고리즘을 사용해야 되는 것으로 보인다. 출력 문단을 살펴보면 3가지 케이스를 구분할 것이 요구됨을 알 수 있다. 도착이 가능할 경우 소지금의 최댓값 도달 자체가 불가능할 경우 "gg" 출력 도착했을 때 돈이 무한으로 발산한다면 "Gee" 출력 이 케이스들을 개별적으로 생각해보자. 첫 번째는 이익이 최대로 되는 경로를 찾으면 된다. 두 번째는 도달 가능성을 판단하면 된다. 세 번째가 생각하기 어려울 수 있는데, 경로를 탐색하던 중 음수 사이클(문제에서는 이익 사이클)로 진입했지만 도달할 수 있는 경로가 존재한다면 돈을 무한정 벌게 되는 것이므로 사이클 존재 여부와 도달 가능성을 판단하면 된다. 즉 세가지를 종.. 이전 1 다음
