프로그래밍 공부 노트

https://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 다익스트라를 살짝 변형한 문제이다. 여우에 대해 다익스트라 탐색을 실행하는 경우와 늑대에 대해 다익스트라 탐색을 실행하는 경우를 따로 생각해야 하는데, 늑대에 대해 다익스트라 탐색을 실행하는 경우 오솔길을 홀수 번 이용하는 경우와 짝수 번 이용하는 경우를 나누어서 계산해야 한다. #include #include #include using n..

그래프 문제를 보다 보면, 특정 노드 a에서 노드 b까지의 경로를 구하는 문제가 자주 보인다. 이런 그래프에서 경로를 구하는 문제에 주로 사용하는 알고리즘이 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이다. 다익스트라는 그래프에 음의 가중치를 갖는 에지가 없을 때 주로 사용한다. 시작 노드에서 특정 경로를 이동해 노드 n에 도착했을 때의 비용을 cost[n]으로 나타낼 때, n에 연결된 i번째 에지 e_i와 e_i에 연결된 노드 n_i에 대해, n_i를 방문하지 않았다면 cost[n_i]가 cost[n] + e_i보다 작을 때 기존 경로를 시작 노드에서 n까지의 경로 + e_i로 갱신하면 더 적은 비용으로 n_i까지 이동할 수 있다. 이 과정을 알려진 경로가 존재하지 않을 때부터 시작해서 더 이상 갱..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 각 지역을 노드, 지역 간의 도로와 그 거리를 에지와 그 가중치로 보면, 이 문제는 모든 노드에서 모든 노드로의 최소 비용을 찾는 문제이므로 플로이드-워셜 기법을 이용해 풀 수 있다. 모든 노드에서 모든 노드로의 경로를 찾은 뒤, 각 노드에서 다른 노드로 이동하는 비용이 m 이하라면 아이템을 획득하고, 획득한 아이템의 최댓값을 출력하면 정답이 된다. #include #define MAX_N 100 #d..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 각 점을 노드로, 수빈이 1초만에 이동 가능한 좌표 간의 관계를 에지로 보면 이 문제는 BFS 문제임을 알 수 있다. 단, 순간이동을 하는 경우 시간 소모가 없으므로 어느 노드를 방문할 때 반드시 해당 노드에서 순간 이동으로 도착할 수 있는 노드를 전부 탐색하여야 한다. #include #include using namespace std; #define MAX_N..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 각 도시를 노드로, 버스를 방향이 있는 에지로 보면 시작점에서 도착점까지 최소 비용과 경로를 묻는 문제이므로 다익스트라를 이용해 풀 수 있다. #include #include #include using namespace std; #define INF 0x3f3f3f3f #define MAX_N 1000 #define _cost first #define _node s..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 각 도시를 노드로, 버스를 방향이 있는 에지로 보면 시작점에서 도착점까지 최소 비용을 묻는 문제이므로 다익스트라를 이용해 풀 수 있다. #include #include #include using namespace std; #define INF 0x3f3f3f3f #define MAX_N 1000 #define _cost first #define _node seco..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 그래프의 시작 노드에서 모든 노드로의 최단 경로를 구하는 문제이므로 다익스트라를 이용해 풀 수 있다. #include #include #include using namespace std; typedef pair edge; #define MAX_V 20000 #define INF 0x3f3f3f3f #define _cost first #define _node s..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1번 노드에서 v1, v2 노드를 순서와 상관없이 거쳐서 N번 노드로 이동하는 문제이다. 1번 노드에서 N번 노드로 이동하는 경로가 항상 v1, v2 노드를 포함하는지 알 수 없으므로 1 -> v1 -> v2 -> N 경로와 1 -> v2 -> v1 -> N 두 경로를 비교해야 한다. 이 때 출발지가 시작점과 두 경유지 v0, v1까지 포함해 총 세 곳..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 각 마을을 노드, 도로를 에지로 보면 그래프 탐색 문제임을 알 수 있다. 그래프에서 특정 노드로 이동하는 최단 비용을 구하는 문제이므로, 다익스트라 기법을 이용해 풀 수 있다. 이 때 중요한 점은, 도로가 단방향 도로이므로 갈 때의 비용과 올 때의 비용이 다르기 때문에 도로를 두 종류로 따로 저장해서 다익스트라를 두 번 실행해야 한다는 것이다. 갈 때의 도로와 올 때..