나그네

6497번: 전력난 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 두 집 사이의 거리만큼의 비용이 드는 가로등이 있고 가로등 불이 켜져 있는 도로로만 이동 가능하도록 유지하면서 최소 비용이 들도록 불을 꺼야 하므로 전체 간선의 가중치에서 최소 스패닝 트리(MST)의 가중치를 빼주면 된다. 코드 #include using namespace std; vector p; int find(int x) { if (p[x] != x) p[x] = find..

4343번: Arctic Network 문제 https://www.acmicpc.net/problem/4343 4343번: Arctic Network The first line of input contains N, the number of test cases. The first line of each test case contains 1 > S >> P; p.resize(P + 1); iota(p.begin(), p.end(), 0); vector edge; vector xy(P + 1); for (int i = 1; i > xy[i].first >> xy[i].second; for (int i = 1; i < P; i++) for (int j = i + 1; j

1414번: 불우이웃돕기 문제 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 변형문제 중 하나로 간선의 가중치가 알파벳으로 입력된다. 문제 조건에 따라 ascii 코드를 기준으로 연산하여 간선을 저장한다. 기부할 수 있는 랜선의 길이는 최소 스패닝 트리의 가중치를 제외한 모든 가중치의 합이므로 간선을 저장할 때마다 cost에 가중치를 더해주고 최소 스패닝 트리의 컴포넌트를 연결할 때마다 간선의 가중치만큼 ..

1833번: 고속철도 설계하기 문제 https://www.acmicpc.net/problem/1833 1833번: 고속철도 설계하기 첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제다. 주어진 인접 행렬에 따라 (i, j)의 값이 양수이면 간선을 추가하고, 음수라면 이미 연결되어 있는 간선이므로 i와 j를 union 해주고 전체 비용에 비용의 절댓값을 추가해 준다. 그리고 인접 행렬은 같은 값이 2번씩 입력되므로 ÷2를 해주어 미리 연결되어 있는 간선들의 가중치를 구해준다. 이제 크루스칼..

14621번: 나만 안되는 연애 문제 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제로 남초 대학교와 여초 대학교를 연결하는 도로로만 이루어져 있으므로 간선을 입력받을 때 한 학교는 남초, 나머지 학교는 여초이면 된다. 따라서 배열을 만들어 각 학교가 남초인지 여초인지 저장하고 간선을 입력받을 때 조건문만 추가해 주면 된다. 그리고 모든 학교를 연결할 수 없는 경..

1185번: 유럽여행 문제 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 풀이 모든 나라를 방문해야 하고 길은 N-1개만 남겨야 하므로 최소 스패닝 트리(MST) 알고리즘을 사용한다. 보통 최소 스패닝 트리 문제는 간선의 가중치가 이동 거리, 시간, 비용 등인데 이 문제에서는 방문한 나라에 도착한 시점에 내는 비용도 고려해야 한다. 따라서 도착한 지점의 비용을 어떻게 처리할 것인지가 문제를 푸는 핵심이다...

4792번: 레드 블루 스패닝 트리 문제 https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 풀이 파란색 간선의 가중치를 1, 빨간색 간선의 가중치를 0으로 해서 간선을 추가한다. 간선을 가중치를 기준으로 오름차순 정렬하여 파란색 간선의 수를 최소로 한 스패닝 트리의 가중치(파란색 간선의 수)를 minBlue, 내림차순 정렬하여 최대로 한 스패닝 트리의 가중치를 maxBlue로 저장한다. minBlue ≤ K ≤ maxBlue를 만족하면 1..

1368번: 물대기 문제 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제로 물을 끌어오는 비용과 우물을 파는 비용을 비교해야 한다. 따라서 가상의 정점을 만들고 i번째 우물을 파는 비용을 가상의 정점과 i번째 정점을 잇는 간선으로 추가해 주면 된다. 그리고 인접 행렬에서 각 정점 간 물을 끌어오는 비용을 간선으로 추가한다. 이제 크루스칼 알고리즘을 사용해 최소 스패닝 트리의..

1774번: 우주신과의 교감 문제 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)를 구하면 된다. 모든 우주신의 좌표를 입력받은 후 서로 간의 거리를 모두 구해 간선으로 추가한다. 이후 이미 연결된 통로인 경우에는 미리 두 점을 union 시켜 MST에서 제외시켜 주고 크루스칼 알고리즘을 사용해 MST를 구한다. 이때 구해지는 가중..

9373번: 복도 뚫기 문제 https://www.acmicpc.net/problem/9373 9373번: 복도 뚫기 각 테스트 케이스마다 센서에 감지되지 않고 복도를 지나갈 수 있는 원형 물체의 최대 반지름을 부동소수점 실수로 한 줄에 출력한다. 물체는 매우 정밀하게 움직일 수 있다고 가정한다. 만약 www.acmicpc.net 풀이 센서에 감지되지 않고 복도를 지나가기 위해서는 각 센서의 감지 범위 바깥으로 지나가야 하고 벽을 벗어날 수도 없다. 우리가 구하고자 하는 것은 끝까지 통과할 수 있는 가장 긴 길이이다. 즉, 작은 간격부터 탐색하다가 특정 조건에서 답이 구해지는 것이다. 풀이에 사용된 방법은 최소 스패닝 트리(MST) 알고리즘이다. 크루스칼(Kruskal) 알고리즘을 사용한 방법으로 문제를..