알고리즘 모음(C++)

문제 링크입니다. 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/2151 2151번: 거울 설치첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net다차원 배열을 이용한 BFS로 풀 수 있는 문제였습니다.두 개의 문이 있을 때, 거울을 이용해 한쪽 문에서 다른 문을 볼 수 있도록 할려고 한다면 몇개의 거울을 사용해야되는지 구하는 문제입니다. 먼저 2개의 문의 위치를 저장한 뒤, 한 쪽 거울에서 BFS 탐색을 시작해줍니다. 여기서는 거울의 설치 갯수를 물어보는 문제이니, 배열 하나를 만들어 큰 값을 저장해줍니다. 그러..

문제 링크입니다. 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/13424 13424번: 비밀 모임입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 1~N번 정점까지 친구들이 있는 곳까지 거리를 각각 구한 뒤, 이를 모두 비교하면 되는 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define INF 21000..

문제 링크입니다. https://www.acmicpc.net/problem/13903 13903번: 출근 첫 번째 줄에는 보도블록의 세로, 가로 R, C(1 ≤ R, C ≤ 1,000)크기가 주어진다. 다음 R개의 줄에는 C개의 문자로 이루어진 보도블록의 초기 상태가 주어진다. (가로 블록은 0로 표시되고, 세로 블록 www.acmicpc.net BFS를 이용한 문제입니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #define INF 987654321 #define F first #define S second using namespace std; int R,..

문제 링크입니다. https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리가 주어졌을 때, 쿼리를 기준으로 자신을 포함한 자식노드의 개수를 구하는 문제입니다. 루트노드는 주어졌기 때문에 루트노드부터 시작해 자식의 개수를 찾으면 됩니다. 간선을 저장할 때, 양뱡향으로 저장하기에 부모와 자식 노드의 구분은 이전에 방문을 했는지 여부를 저장하는 check 배열을 통해 했습니다. 자식노드일 경..