4Legs_Archives

문제 링크 : www.acmicpc.net/problem/8452 8452번: 그래프와 쿼리 첫 번째 줄에 그래프의 정점, 간선의 수와 질의의 수를 나타내는 n, m, q 가 주어진다. (1 ≤ n ≤ 1, 000, 1 ≤ m ≤ 100, 000, 1 ≤ q ≤ 200, 000) 정점들은 순서대로 1부터 n까지 번호가 매겨져 있고, 간선들 www.acmicpc.net 문제 유형 BFS, Dijkstra, 오프라인 쿼리 오프라인 쿼리(Offline Query)란, 주어지는 쿼리들을 받는 즉시 처리하지 않고 모두 저장해둔 뒤 임의의 순서로 쿼리를 해결하는 기법을 말한다. 이 문제에서는 모든 쿼리를 다 받은 뒤, 쿼리를 역순으로 처리함으로써 문제를 간단화하여 해결할 수 있다. 즉, 원래의 U k 쿼리는 그래프..

문제 링크 : www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 문제를 자세히 읽지 않는다면 최소 스패닝 트리(MST) 문제로 혼동할 수 있다. 제시된 조건 중, "따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다." 라는 내용이 있기 때문에 이 문제는 최소 스패닝 트리로 해결할 수 없게 된다. 다음과 같은 반례를 들 수 있다. 그림에서 붉은 색으..

문제 링크 : www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 문제에서 제시된, "세금이 인상될 때 최단거리가 갱신되는 경우"란 무엇일까? 세금이 인상되지 않았을 때 최단거리를 이미 알고 있다는 가정에서 생각해보자. ① 세금이 인상될 때, 어떤 한 경로에 대해 비용의 상승은 무엇에 의해 결정될까? 이는 해당 경로에 포함된 간선의 개수와 관련된다. 즉, 세금이 k원 인상될 때, 간선을 m..

문제 링크 : 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 다익스트라 알고리즘을 적용해 각 정점에 대한 K번째 최단경로의 가중치 합을 구하는 문제이다. 일반적인 다익스트라 알고리즘에서는 우선순위 큐(최소 힙)에서 pop되는 순간 그 정점에 대한 최소 가중치 합은 고정된다. (다익스트라 알고리즘 참조 : 4legs-study.tistory.com/21) 다익스트라 알고리즘은 기본적으로 최단거리를 구하..

문제 링크 : www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 어떠한 도시에 도착했을 때, 몇 개의 도로를 포장해서 이동했는지는 구별되어야 한다. 이전 포스팅인 BOJ16118_달빛 여우 문제처럼 가중치에 어떤 요소가 더해졌을 때는 이를 구별하기 위해 DP를 섞어 사용한다. 따라서, dist 배열을 dist[n][k]와 같은 이차원 배열 형태로 구성해 문제를 해결하자. dist[i][j] = i번 도시에 j개의 도로를 포장..

문제 링크 : www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 가중치를 번갈아 x2, /2 하여 이동하도록 하는 다익스트라 알고리즘을 구현하는 문제이다. 우선 가중치의 /2에 값이 유실되지 않도록 그래프의 가중치는 입력값의 2배로 설정한다. 기존 다익스트라 알고리즘의 우선순위 큐에 인자를 추가하여, (이 풀이에선 sprint 이다.) 해당 인자의 값에 따라 다익스트라 내의 새 dist에 x2 또는 /2..

문제 링크 : www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 결국 문제는 특정한 하나의 간선을 출발지로부터의 최단경로에 포함하는 노드들을 구하는 것이다. 후술할 다른 풀이방법도 있지만, 문제의 의도에 따라 다익스트라 알고리즘을 적용해 정석으로 풀이해보자. 위의 예제 그래프에서 2번 노드에서 어떤 목적지 후보 노드에 대한 최단경로가 1-3 간선을 포함하고 있다면, 1번 노드에서 그 목적지 후보 노드에 대한 최단거리는 출발 노드로부터 목적지 후보 노드까지..

[서론] 그래프 최단경로 알고리즘으로, 꽤 자주 보이는 유형이다. 다익스트라 알고리즘은 음수가 아닌 가중치가 있는 그래프에서 한 점으로부터 다른 모든 점까지의 최단 경로를 구하는 알고리즘이다. [동작 원리] 다음과 같은 그래프에서, 1번 노드와 나머지 각 노드 간의 최단거리를 다익스트라 알고리즘을 통해 구해보자. 다익스트라 알고리즘은 위와 같은 상태에서 시작한다. 테이블의 값은 출발 노드로부터 해당 노드까지의 최소 가중치 합을 의미하며, 테이블의 값이 INF(무한대)라면 해당 노드와 연결되어 있지 않다는 의미이다. 아직은 1번 노드만 확인했으므로, 다른 모든 노드에 대해 INF가 기록된 모습이다. 출발 노드로부터 인접한 각 노드에 대해 테이블에 거리를 기록한다. 예시 그래프에서는 출발 노드 1이 2, 3..