알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 최소 스패닝 트리를 이용한 문제입니다. C에서 V까지 가는데 비용이 최대가 되도록 만들어주는 것이 핵심입니다. 따라서 기존 최소 스패닝 트리와 달리, 정렬을 비용을 기준으로 내림차순으로 해주면 됩니다. 처음에는 X번째 connect 배열에 X값을 넣어줍니다. 해당 배열을 통해서 X가 어디에 연결되어 있는지를 저장합니다. X와 Y..

문제 링크입니다. https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net BFS와 MST를 이용해 푸는 문제입니다. 저는 이 문제를 한 구역에서 다른 구역까지의 거리 최솟값을 저장한 뒤, Union-Find를 이용해 구했습니다. 로봇은 언제 생성하든 시간이 들지 않기에, MST를 통해 최솟값을 구하면 자연스럽게 풀리는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #..

문제 링크입니다 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net MST를 두번 실행하면 풀리는 문제였습니다! 문제 접근 방법 1. 출발점, 도착점, 비용을 백터에 저장한다. 2. 비용에 대해서 내림차순으로 먼저 정렬한다.(1 -> 내림막길임으로 내림차순으로 했습니다) 3. 최소 비용을 구한다. 4. 비용에 대해서 오름차순으로 정렬한다. 5. 최대 비용을 구한다. 간단한 MST 문제임으로 자세한 것은 코드를 참고해주세..

문제 링크입니다 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 크루스칼 알고리즘을 사용하면 쉽게 풀리는 문제였습니다! 1번 도시는 정복하고 있기에 1번에서 최소 비용으로 갈 수 있는 곳을 먼저 정복한 뒤 Union+Find를 해주면 되는 문제였습니다! 문제 접근 방법 1. 백터에 시작점과 끝점, 비용을 저장한다. 2. 비용에 대해서 오름차순으로 정렬한다. 3. 1번 도시를 찾은 후, 먼저 연결해주고 시작한다. 4. Union+Find를 통해서 모..

문제 링크입니다 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net MST 문제였습니다. Union() + Find()를 할 때 기존과 다르게 Union 부분에서 조건을 걸어줘야 했던 문제였습니다. 문제 접근 방법 1. 발전소의 번호를 입력받을때, 배열을 하나 만들어서 해당 지점에 발전소가 있다는 것을 표시한다. 2. 간선들의 정보를 입력받고, 비용에 따라 오름차순으로 정렬한다. 3. 정렬한 간선들의 갯수..

문제 링크입니다 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 2차원 공간에서의 최소 비용 구하기와 다르게 3차원이면서 N의 범위도 100,000 까지이기에 까다로운 문제였습니다. 방법을 생각하는데 꽤 오래걸린 것 같습니다.(괜히 골드1 문제가 아니였습니다) 문제 접근 방법 1. 각 좌표들을 입력받는다.(저는 구조체로 입력받았습니다) 2. 좌표들을 X, Y, Z축에 따라 오름차순으로 정렬한다. 3. 각 축으로 ..

문제 링크입니다 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 쿠르스칼 알고리즘을 사용해서 풀었습니다. 문제 접근 방법 1. 각 학교가 남초 대학인지 여초대학인지 알 수 있는 배열을 선언해 값을 저장합니다. 2. 구조체 백터를 통해서 출발점, 도착점, 비용을 저장한뒤, 비용값에 따라 오름차순으로 정렬합니다. 3. 백터의 처음부터 마지막까지 for문을 돌립니다. 4. for문 안에서 출발점과 도착점이 서..

문제 링크입니다 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 간단한 MST 문제였습니다. 본격적인 쿠르스칼 알고리즘을 실행하기 전에 연결되어 있는 지점들을 연결해주고 시작하는게 포인트였습니다. for (int i = 0; i > x >> y; Union(x, y); } 연결되어 있는 지점을 입력 받은 뒤에 Union함수를 통해서 연결해줬습니다. for (..

문제 링크입니다 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 간단한 MST 문제였습니다. 플로우 관리비용이 10억까지 있어, long long을 써주는 것만 주의하면 되는 문제였습니다. Union + Find 함수를 이용해 Kruskal 알고리즘을 구현했습니다. -> 이것만 할 수 있으면 푸는 문제입니다 자세한 것은 코드를 참고해주세요! #include #include #include #include #include #include #inc..

문제 링크입니다 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 간단한 MST문제였습니다. 문제 접근 방법 1. 백터를 통해서 좌표를 입력 받는다. 2. 1번 좌표에서 갈수 있는 다른 별들의 거리를 저장한다. ex) 1번에서는 2,3,4,5...등 갈수 있습니다. 따라서 구조체 백터에 시작점, 도착점, 거리를 저장한다. 2번의 경우에는 3,4,5,6...등을 갈 수 있습니다. 1번과 똑같이 저장한다. 3. cost의 값에따라 오름차순으로 정렬한다..