백준/그래프 (22) 썸네일형 리스트형 [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와 도착점에 연결된 간선의 길이 를 만족한다면 그 간선은 최단 경로에 포함되는 간선이 된다. 해당 간선으로는 통행할 수 없도록 하자. 또한 최단 경.. [ICPC] 백준 9019 - DSLR www.acmicpc.net/problem/9019 주어진 명령어 D, S, L, R을 수행하여 초기 레지스터부터 목표 레지스터까지 최소 연산 횟수를 구하는 문제이다. 각 명령어 4개를 수행한 상태를 지금까지 연산한 횟수와 함께 큐에 넣어 목표 레지스터에 도달했을 때 최소 연산 횟수를 출력하면 된다. 시키는대로 BFS를 돌리면 되겠으나 문제는 L과 R인데 두 명령을 효율적으로 수행하지 않으면 TLE를 받게 된다. 작성자는 초기에 스트링으로 변환하여 옮기기, deque에다 각 자리 숫자를 넣어주기와 같은 방법을 시도하였으나 이는 전부 TLE를 받게 되고 아래와 같이 곱하기 나누기 연산을 통해 수를 바꿔주어야 제한 시간 내로 통과할 수 있다. // cur.first는 현재 레지스터이다. int l = cur.. 이전 1 2 3 4 5 다음
