전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/1486 1486번: 등산첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000www.acmicpc.net다익스트라를 2번 이용해 푸는 문제입니다. 높이를 의미하는 알파벳이 주어지고 N*M이 주어질 때, 세준이가 오를 수 있는 가장 높은 높이를 구하는 문제입니다. 세준이는 (1, 1)에서 시작하고, 높이의 차는 ‘T’이하만 이동할 수 있습니다. 다른 위치로 이동할 때 드는 시간은 1. 현재 위치보다 낮은 곳을 이동할 경우 -> 1 2. 현재 위치보다 높은 곳을 이동 -> ..

문제 링크입니다. https://www.acmicpc.net/problem/11952 11952번: 좀비첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2,www.acmicpc.net다른 목적을 가진 다익스트라를 2번 사용해 푸는 문제였습니다.좀비가 점령한 도시가 있을 때, 다른 도시들을 거쳐 N번 도시로 갈 수 있는 최소 비용을 구하는 문제입니다. 점령된 도시와 거리가 S 이하인 도시는 숙박비를 q로, 아닌 도시는 p로 받습니다. 먼저, 도시들이 점령 당한 도시들로부터 얼마나 떨어져 있는지를 구해야 합니다. 여기..

문제 링크입니다. https://www.acmicpc.net/problem/13911 13911번: 집 구하기첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사www.acmicpc.net다익스트라를 시작할 때, 맥도날드 정점과 스타벅스 정점을 각각 전부 넣고 시작하는 문제였습니다. 맥도날드의 위치들과 스타벅스의 위치들이 주어질 때, 두 가게의 거리의 합이 최소가 되는 지점의 번호를 출력하는 문제입니다. 먼저 맥도날드와 스타벅스로 부터 떨어져 있는 거리를 구해야합니다. 가게가 하나가 아닐 수도 있기에, 어떤 지점을 ..

문제 링크입니다. https://www.acmicpc.net/problem/16681 16681번: 등산첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net다익스트라를 양쪽에서 이용해 푸는 문제입니다.목표 지점을 정해, 집에서 목표지점까지는 높이를 무조건 올라가게, 목표지점부터 고려대학교까지는 높이를 무조건 내려가는 방식으로 할 때, 얻을 수 있는 최대 가치는 얼마인지 구하는 문제입니다. N의 갯수가 100,000이기에, 목표지점 하나마다 경우를 확인해보기에는 경우가 많아 시간초과가 됩니다. 따라서, 시작지점과 끝점에서 시작에..

문제 링크입니다. https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 730에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다.www.acmicpc.net다차원 배열을 사용하는 다익스트라 문제입니다.소가 길을 건널 때, 주어진 조건에 따라 최소 시간을 구하는 문제입니다. (1, 1) ->(N, N)으로 가면서, 3번째 방문하는 곳은 항상 풀을 먹어야 합니다. 이동할 때마다 이동시간 T가 추가됩니다. 항상 최단 횟수로 갔을 때, 최소 비용이 나온다는 보장을 할 수 없습니다.(위의 예시가 그렇습니다.) 따라서 다익스트라를..

문제 링크입니다. https://www.acmicpc.net/problem/17270 17270번: 연예인은 힘들어첫 번째 줄에는 약속 장소 후보의 수 V와 약속 장소를 연결하는 총 길의 수 M이 주어진다. (2 ≤ V ≤ 100, 1 ≤ M ≤ 1,000) 그리고 다음 M개의 각 줄에는 a, b, c 가 주어진다. a, b는 길의 시작과 끝이www.acmicpc.net다익스트라를 이용해 풀 수 있는 문제였습니다.지헌이와 성하가 만날 때, 최적의 장소를 구하는 문제입니다. 최적의 장소는 구하는 방법은 1. 둘이 만날 때, 거리는 최소가 되어야 합니다. 2. 출발지는 장소 후보에서 제외됩니다. 3. 지헌이가 성하보다 더 일찍 도착해야 합니다. 4. 위의 조건을 모두 만족하는 장소가 있다면, 지헌이한테 가장..

문제 링크입니다. https://www.acmicpc.net/problem/23801 23801번: 두 단계 최단 경로 2첫째 줄에 정점의 수 N (10 ≤ N ≤ 100,000), 간선의 수 M (10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타www.acmicpc.net다익스트라를 사용하는 문제입니다.무조건 들려야하는 점이 존재할 때, 해당 점을 하나라도 들리면서 갈 수 있는 최소 비용 경로를 구하는 문제입니다. 들려야하는 점의 갯수가 최대 N-3개이니 100,000개 정도가 주어집니다. 따라서, X->K + K->Z를 점마다 확인하는 것은 시간 초과가 될 것입니다.(K를 들려야 하는 점으로 ..

문제 링크입니다. https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳$N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할www.acmicpc.net다익스트라를 이용하는 문제입니다.1 ~ N까지 중에서, 친구의 위치가 3개가 주어질 때, 최소 거리가 가장 긴 위치를 찾는 문제입니다. 1부터 시작해 1->1 ~ 1->N,,,,,,N->1 ~ N->N까지 모든 경우를 구한 뒤, 3지점까자의 각각의 거리를 비교해서 최솟값을 찾는 것은 다익스트라를 100,000번 돌려야 되기 때문에 시간초과가 생기게 됩니다. 따라..

문제 링크입니다. https://www.acmicpc.net/problem/20007 20007번: 떡 돌리기첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y 다익스트라를 통해 거리를 구한 뒤, *2를 하면 됩니다. 거리가 가장 짧은 곳부터 오름차순으로 방문하기 때문에 거리를 구한 뒤, 정렬을 해주면 됩니다...

문제 링크입니다. https://www.acmicpc.net/problem/23793 23793번: 두 단계 최단 경로 1서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으www.acmicpc.net다익스트라를 이용한 문제입니다.문제 시간이 0.3초이며, N과 M의 값이 큰 만큼, 시간을 생각하면서 풀어야하는 문제입니다. 먼저, 문제를 풀기 위해 방향을 생각해보겠습니다. 두개를 출력하면 됩니다. 1. X -> Y -> Z를 들려서 올 때의 최소 비용 2. X -> Z(Y를 제외)로 올 때의 최소 비용 2번은 간단합니다. 다익스트라를 실행할 때, Y점에 도달한다면, 해당 경우를..

문제 링크입니다. https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net다익스트라 알고리즘을 활용한 문제입니다.문제를 풀기 위해선 1->N 점까지 가는 최단 거리가 1->민준->N 점으로 가는 최단거리와 같은 것인지를 알아야 했습니다. ->이 두 경우의 값이 같다면 항상 민준이는 건우를 도울 수 있기 때문입니다. 따라서 1->N까지 가는 다익스트라로 원래 최단 거리를, 1->민준 + 민준->N의 최단 ..

문제 링크입니다. https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net다익스트라를 이용하는 문제입니다.가중치가 주어졌을 때, 연결할 수 있는 최솟값을 출력하는 문제입니다. 연결했을 때의 최솟값만 출력하면 되기에 다익스트라 알고리즘을 이용해서 풀어주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #i..