최단 경로 (21) 썸네일형 리스트형 백준 2617번 [구슬 찾기](C++) -yes6686- 티스토리 백준 문제 풀이: 2617 (구슬 찾기)문제 링크: https://www.acmicpc.net/problem/2617문제 설명:각 구슬의 무게가 서로 다르며, 일부 구슬들 사이의 비교 결과가 주어졌을 때, 특정 구슬의 무게가 전체에서 중간이 아님을 판별하는 문제입니다. 즉, 어떤 구슬이 n개의 구슬 중 정확히 중간보다 무거운지/가벼운지를 확정할 수 없는지를 판별합니다.구슬 수 N(≤100), 비교 결과 수 M(≤N(N-1)/2)이 주어지고, 모든 구슬을 대상으로 탐색하면서 절반 이상 무겁거나 가벼운 구슬 수를 구해 조건에 만족하면 해당 구슬은 중간이 될 수 없습니다.문제 해결 코드// 구슬 찾기 (양방향 DFS 탐색)#include #include #include using namespace std;ve.. 백준 13549번 [숨바꼭질 3](C++)-yes6686- 티스토리 백준 문제 풀이: 13549 [숨바꼭질 3]문제 링크: https://www.acmicpc.net/problem/13549문제 설명:수빈이가 위치 n에 있고, 동생은 위치 k에 있습니다. 수빈이는 1초 후 다음 중 하나의 행동을 할 수 있습니다:n - 1로 이동n + 1로 이동n * 2로 이동 (이동 시간은 0초)수빈이가 동생을 찾는 데 걸리는 최소 시간을 출력합니다.입력:첫째 줄에 정수 n과 k가 주어집니다. (0 ≤ n, k ≤ 100,000)출력:첫째 줄에 수빈이가 동생을 찾는 최소 시간을 출력합니다.문제 해결 코드#include #include using namespace std;const int MAX = 100001;int visited[MAX];void bfs(int start, int ta.. 백준 11779번 [최소비용 구하기 2](C++)-yes6686- 티스토리 백준 문제 풀이: 11779 [최소비용 구하기 2]문제 링크: https://www.acmicpc.net/problem/11779문제 설명:n개의 도시와 m개의 버스가 주어질 때, 특정 시작 도시에서 특정 도착 도시까지의 최소 비용을 구하고, 그 경로를 출력하는 문제입니다.입력:첫째 줄에 도시의 개수 n (1 ≤ n ≤ 1,000)과 버스의 개수 m (1 ≤ m ≤ 100,000)이 주어집니다.다음 m개의 줄에는 세 개의 정수 a, b, cost가 주어지며, 이는 도시 a에서 도시 b로 가는 비용이 cost임을 의미합니다.마지막 줄에는 출발 도시와 도착 도시가 주어집니다.출력:첫째 줄에 최소 비용을 출력합니다.둘째 줄에 최소 비용으로 이동하기 위한 경로에 포함된 도시의 개수를 출력합니다.셋째 줄에 최소 .. 백준 11404번 [플로이드](C++)-yes6686- 티스토리 백준 문제 풀이: 11404 [플로이드]문제 링크: https://www.acmicpc.net/problem/11404문제 설명:n개의 도시와 도시를 연결하는 m개의 버스가 주어질 때, 모든 도시 간의 최소 비용을 구하는 문제입니다. 주어진 입력은 방향 그래프이며, 간선의 가중치가 존재합니다. 출력은 도시 i에서 도시 j로 이동하는 데 드는 최소 비용을 나타내는 n × n 행렬입니다. 만약 갈 수 없다면 0을 출력합니다.입력:첫 번째 줄에 도시의 개수 n (2 ≤ n ≤ 100)이 주어집니다.두 번째 줄에 버스의 개수 m (1 ≤ m ≤ 100,000)이 주어집니다.다음 m개의 줄에는 출발 도시, 도착 도시, 비용이 주어집니다.출력:i에서 j로 가는 최소 비용을 나타내는 n × n 행렬을 출력합니다. 갈.. 백준 1916번 [최소비용 구하기](C++) -yes6686- 티스토리 백준 문제 풀이: 1916 [최소비용 구하기]문제 링크: https://www.acmicpc.net/problem/1916문제 설명:n개의 도시가 주어졌을 때, 출발 도시에서 도착 도시로 가는 최소 비용을 구하는 문제입니다. 각 도시는 버스로 연결되어 있으며, 비용이 다릅니다.입력:첫 번째 줄에 도시의 개수 n (1 ≤ n ≤ 1,000)와 버스의 개수 m (1 ≤ m ≤ 100,000)가 주어집니다.다음 m개의 줄에는 버스의 출발 도시 a, 도착 도시 b, 비용 c가 주어집니다. (1 ≤ c ≤ 100,000)마지막 줄에는 출발 도시 start와 도착 도시 last가 주어집니다.출력:출발 도시에서 도착 도시로 가는 데 드는 최소 비용을 출력합니다.예제:입력:5 81 2 21 3 31 4 11 5 102.. 백준 1865번 [웜홀](C++) -yes6686- 티스토리 백준 문제 풀이: 1865 [웜홀]문제 링크: https://www.acmicpc.net/problem/1865문제 설명:여러 개의 마을과 마을을 잇는 도로 및 웜홀이 있을 때, 웜홀을 이용해 시간이 음수인 사이클을 형성할 수 있는지를 판별하는 문제입니다.입력:첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 ≤ T ≤ 5)각 테스트 케이스의 첫 줄에는 마을의 수 n, 도로의 수 m, 웜홀의 수 w가 주어집니다. (1 ≤ n ≤ 500, 1 ≤ m ≤ 2,500, 1 ≤ w ≤ 200)다음 m개의 줄에는 두 마을을 잇는 도로 정보 s e t가 주어지며, 이는 s에서 e로 가는 시간이 t임을 나타냅니다.다음 w개의 줄에는 웜홀 정보 s e t가 주어지며, 이는 s에서 e로 가는 시간이 -t임을 나.. 백준 1753번 [최단경로](C++) -yes6686- 티스토리 백준 문제 풀이: 1753 [최단경로]문제 링크: https://www.acmicpc.net/problem/1753문제 설명:방향 그래프가 주어졌을 때, 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제입니다. 만약 특정 정점으로 가는 경로가 없다면 "INF"를 출력합니다.입력:첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어집니다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)둘째 줄에 시작 정점의 번호 K가 주어집니다. (1 ≤ K ≤ V)셋째 줄부터 E개의 줄에 간선 정보 u v w가 주어집니다. (1 ≤ u, v ≤ V, 0 ≤ w ≤ 10)출력:첫째 줄부터 V개의 줄에 각 정점으로 가는 최단 경로의 값을 출력합니다. 경로가 존재하지 않으면 "INF"를 출력합니다.예시:입력.. 백준 1504번 [특정한 최단 경로](C++) -yes6686- 티스토리 백준 문제 풀이: 1504 [특정한 최단 경로]문제 링크: https://www.acmicpc.net/problem/1504문제 설명:1번 정점에서 N번 정점으로 이동하는 최단 경로를 구하되, 반드시 두 정점 v1과 v2를 통과해야 합니다. 가능한 경로 중 최단 거리를 출력합니다. 경로가 존재하지 않는 경우 -1을 출력합니다.입력:첫째 줄에 정점의 개수 n과 간선의 개수 m이 주어집니다. (2 ≤ n ≤ 800, 0 ≤ m ≤ 200,000)둘째 줄부터 m개의 줄에 간선의 정보 a, b, cost가 주어집니다. (1 ≤ cost ≤ 1,000)마지막 줄에 반드시 거쳐야 하는 두 정점 v1과 v2가 주어집니다.출력:1번 정점에서 N번 정점으로 가는 최단 경로 중 v1과 v2를 반드시 지나는 최단 거리를 출.. 이전 1 2 3 다음