문제 https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 최소 스패닝 트리(MST)를 적용하여 해결하는 문제. 처음에는 어떤 부분이 MST 문제인지도 감을 못 잡아서 결국 다른 분의 풀이를 보고 해결했다. 4Legs_Archives님의 [백준]레드 블루 스패닝 트리 풀이 문제의 풀이는 난이도에 비해 간단하지만 증명을 어떻게 유도하는 것이 어려웠다. 일단 풀이는 다음과 같다. 1. 파란 간선의..

문제 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 풀이 solved.ac 난이도: Platium 4 간선의 가중치를 알맞게 변경시켜주어야 해결할 수 있는 최소 스패닝 트리(MST) 문제. 일단 문제를 읽어보면 MST 문제임을 알리는 힌트를 준다. N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야 할 것이다. 하지만 문제의 힌트를 읽어보..

문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 단순한 최소 스패닝 트리 알고리즘의 적용으로는 해결할 수 없는 문제. 모든 행성을 연결하는 최소 비용을 구해야 하므로 최소 스패닝 트리(MST, Mininum Spanning Tree)를 구해야 한다. 간선의 정보는 직접 주어지지 않고 행성(정점)들의 위치를 통해 계산해야 하는데 모든 행성끼리 서로 간선을 잇게 되면..

문제 https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 BFS를 이용하여 떨어진 열쇠들과 시작 위치의 최단 거리를 구하여 간선으로 이어준다음, 최소 스패닝 트리(Minimum Spanning Tree)를 구하는 문제. 문제가 약간 특이한 편이지만 잘 읽어보면 로봇은 결국 열쇠들로 이동할 때는 최단 경로(거리)로 이동하는 것이 항상 최선의 방법임을 알 수 있다. 열쇠나 시작..

문제 https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 플로이드-와샬 알고리즘과 브루트 포스로 해결한 문제. 다익스트라로도 해결 가능하지만 개인적으로는 플로이드-와샬(Floyd-Warshall) 최단 경로 알고리즘을 이용하는 것이 더 깔끔한 것 같다. 문제 해결을 위해서는 두 가지 정보가 필요하다. 1. 각 정점에서 모든 정점까지의 최단 경..

문제 https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 주어지는 그래프에서 간선을 통해 서로 도달 가능한 정점끼리 하나의 위원회(컴포넌트)를 이루게 하여 해결하는 플로이드-와샬 문제이다. 이 문제에서 플로이드-와샬(Flody-Warshall) 최단 경로 알고리즘이 적용되는 부분은 다음과 같다. 위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하시오. 위원..

문제 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 모든 두 정점 쌍 사이의 거리를 구하는 플로이드-와샬(Floyd-Warshall) 최단 경로 알고리즘을 조금 변형해서 푸는 문제. 플로이드 알고리즘은 두 정점의 최단 거리를 구하지만 만약 두 정점 사이의 경로가 없다면 dist의 초기화 값이 INF값이 그대로 남게 된다. 즉, adj[i][j]의 초기화 값이 그대로 남았다면..

문제 https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 2차원 좌표의 각각을 정점으로 생각하여 해결하는 벨만-포드 최단 경로 알고리즘 문제. 이번 문제처럼 벨만-포드 문제의 특징은 최단 경로를 구하되 음의 간선(가중치가 마이너스값)이 주어질때 음의 사이클이 구성이 되는지 판정한다. 음의 사이클이 존재하는 경우 상근이는 계속 과거로 돌아갈 수 있으므로 Never를 출력해야 한다. 2차원 좌표계에서 그래프..

문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 다익스트라는 음수 사이클의 존재 여부를 알 수 없으므로 음수 사이클의 존재 여부를 판정할 수 있는 벨만-포드(Bellman-Ford) 최단 경로 알고리즘을 사용하자. 벨만-포드 알고리즘이 음수 사이클의 존재 여부를 알 수 있는 이유는 다음과 같다. 벨만-포드에서는 모든 정점에서 간선으로 연결된 정점으로 이동하는 거리의 완화를 시도한다...

문제 www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 단일 시작점 최단경로 알고리즘의 대표 격인 다익스트라는 음수 가중치의 간선이 있는 그래프에서는 정확한 값을 구할 수 없다. 그 이유는 음수 사이클이 반복된다면 우선순위 큐에 음의 최단 거리를 가지는 정점이 무한히 업데이트되며 삽입될 것이다. 따라서 이번 문제와 같이 간선의 가중치로 음수가 주어지는 경우..