https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net BFS 문제. bfs를 함에 있어서 위치에 따라 이동거리가 바뀐다는 점에 유의해서 작성해주면 ..

다익스트라 알고리즘의 활용 문제 처음에는 각 면접장마다 다익스트라를 K번 돌리려고 생각했었는데, 이 경우에는 면접장의 개수가 많기 때문에 TLE를 받게 된다. 다익스트라를 한번만 돌리되 처음에 넣는 노드를 K개 넣어주어야 한다. 모든 면접장과 거리 0으로 연결되는 가상의 도시를 하나 만든다고 생각해도 무난하다. 다익스트라를 돌리고 난 뒤의 거리는 각 도시에서 가장 가까운 면접장으로 가는 거리값과 같으므로 이 거리 배열을 순회하면서 최대값을 구해주면 AC를 받을 수 있다. 이때 주의해야 할 점은 탐색방향이 반대가 되므로 방향그래프의 방향도 모두 뒤집어줘야한다는점? 이거때문에 좀 고생좀했습니다. 그리고 범위가 int범위를 넘어갈수있으니 long long 형을 사용해주도록 하자. #include #define..

프림 / 크루스칼 알고리즘을 사용하면 쉽게 해결할 수 있다. 나는 크루스칼 알고리즘을 사용했다. www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘의 기본적인 구현을 묻는 문제 더보기 #include using namespace std; typedef long long int ll; struct line{ int s; int e; int w; }; vector g; int parent[12345] ..

누가봐도 다익스트라같이 생긴 문제이고, 실제로 다익스트라를 빠삭하게 이해하고 있다면 해결할수 있는 문제였다. www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라는 탐색 도중에서 의도적으로 최단경로가 아닌 경우를 배제하는데, 이 배제되는 경로들을 전부 잘 저장해두고 정리해주면 된다. if(ans[next].size() < k){ pq.push({-(dist+dis), next}); ans[next..