백준/그래프 (23) 썸네일형 리스트형 백준 20530 - 양분 noj.am/20530 풀이 문제에 언급된 그래프는 다음과 같은 모양을 가질 수 있다. 이들의 공통점은 사이클이 하나 존재한다는 것이다. 따라서 단순 경로의 갯수는 u에서 v로 가다가 두갈래 길을 만나냐 만나지 않느냐로 갈린다. 따라서 오직 2와 1만 답이 될 수 있다. 두갈래로 나뉘는지 아닌지 어떻게 알 수 있을까? 만약 두 노드가 사이클을 경유하지 않으면 1이다. 길이 하나만 있을 수 밖에 없다. 두 노드가 사이클을 경유하는 경우를 살펴보자. 두 노드가 사이클에 속한 경우는 무조건 두 갈래로 탐색할 수 있기 때문에 2이다. 두 노드가 사이클에 속하지 않은 경우도 2다. 탐색하다 사이클을 만나 두갈래로 나눠지기 때문이다. 한 노드만 사이클에 속한 경우는 조금 복잡하다. 다음 그래프를 보자. 다음 그래프.. [USACO] 백준 15591 - MooTube (Silver) www.acmicpc.net/problem/15591 N, Q > n >> q; vector al(n + 1); for (int i = 0; i > go >> to >> val; al[go].push_back({to, val}); al[to].push_back({go, val}); } while (q--) { int k, from; cin >> k >> from; cout 백준 1738 - 골목길 icpc.me/1738 문제 분석 가는 길마다 돈을 갈취당하거나 주울 수 있다. 갔던 곳을 또 가도 똑같은 일이 일어난다. 최적의 경로는 보유금을 최대로 한 채로 콘도에 도착하는 경우이며 최적의 경로에 도달할 수 없는 경우가 있다고 한다. 다음을 생각해볼 수 있다. 1. 콘도에 못가는 경우 : 당연하게도 경로 자체가 없으면 콘도에 갈 수 없다. 2. 가는 길에 돈을 얻는 사이클이 있는 경우: 민승이는 최대 보유금을 위해 돈을 줍느라 최대 보유금은 양의 무한대로 발산하므로 콘도에 영영 도착할 수 없게 된다. 이 내용들을 고려하여 금액을 가중치로 바꾸면 음수의 가중치를 처리할 수 있는 알고리즘이 필요하다. 벨만포드/SPFA로 풀어보자. 구현 콘도에 갈 수 없는 경우를 미리 처리해주자 $n \leq 100$ .. 백준 11779 - 최소비용 구하기 2 http://icpc.me/11779 출발 도시에서 도착 도시까지 최소비용을 구하는 문제이며, 이는 다익스트라 알고리즘을 그대로 적용할 수 있다. 하지만 최소비용뿐만 아니라 최소비용이 되기 위한 경로도 출력할 것을 요구하고 있다. 알아야 할 것 최단 경로의 해는 다익스트라 알고리즘을 수행하면서 배열로 저장할 수 있다. 우선순위 큐에서 꺼낸 노드 A와 A가 연결된 노드 B가 최적해를 갱신할 때 그 노드를 배열에 저장해주면 된다. 이렇게 하면 실제 최단 경로의 역순으로 노드가 구성된다. 구현 최단 경로를 저장하면서 다익스트라 알고리즘을 수행한 후, 저장된 최적해를 거꾸로 출력해주면 AC를 받을 수 있다. 전체 코드 더보기 #include using namespace std; using ll = long lo.. [ICPC] 백준 5719 - 거의 최단 경로 http://icpc.me/5719 Step 1. 최단 경로를 구해보자. 다익스트라를 통해 어렵지 않게 구할 수 있다. 만약 경로를 못찾으면 거의 최단 경로라는 말 자체에 모순이 있는 것이므로 -1를 출력해주자. 노드 간 간선이 최대 하나 존재할 수 있다는 설명과 후술할 step 2를 고려하여 인접행렬로 그래프를 구성하여 구성하자. 다익스트라를 통해 구한 시작점부터 각 정점까지의 길이는 따로 저장할 수 있도록 하자. Step 2. 도착점부터 시작점까지 bfs를 통해 거슬러 올라가도록 한다. 올라가는 과정에서 도착점까지의 길이 = 정점 i까지의 길이 + 정점 i와 도착점에 연결된 간선의 길이 를 만족한다면 그 간선은 최단 경로에 포함되는 간선이 된다. 해당 간선으로는 통행할 수 없도록 하자. 또한 최단 경.. 이전 1 2 3 4 5 다음
