*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. [알고스팟] 근거리 네트워크(LAN) + 프림 - 하 [백준] 복제 로봇(1944) + 크루스칼 - Gold2 [백준] 행성 터널(2887)★ + 크루스칼 - Gold1 [백준] 유럽 여행(1185) + 크루스칼 - Platium 4 [알고스팟] 여행 경로 정하기(TPATH)★ + 크루스칼 - 상 [백준] 레드 블루 스패닝 트리(4792)★ + 사이값 판정 - Platium 3

문제 https://algospot.com/judge/problem/read/TPATH algospot.com :: TPATH 여행 경로 정하기 문제 정보 문제 당신은 철도망을 이용해 한 도시에서 다른 도시까지 여행을 하고 싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의 algospot.com 풀이 종만북 난이도: 상 최소 스패닝 트리(MST, Minimum Spanning Tree)을 잘 응용해야 풀 수 있는 문제. MST 문제임에도 0번 도시에서 N-1번 도시까지의 경로 중 속도 차이의 최솟값을 묻고 있다. 최단 경로와는 다르게 경로들 중에서 최대 속도와 최소 속도의 차가 최소가 될 수 있게 만드는 길을 찾고 있다. 이런 문제에서 MST를 어떻게 이용해야 할..

문제 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://algospot.com/judge/problem/read/LAN algospot.com :: LAN 근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일 algospot.com 풀이 종만북 난이도: 하 모든 건물들이 같은 컴포넌트에 속하도록 새로 연결하는 간선들의 최솟값을 구하는 문제이므로 최소 스패닝 트리(Minimum Spanning Tree) 문제이다. 최소 스패닝 트리를 해결하기 위한 알고리즘은 대표적으로 두 가지가 존재한다. 1. 크루스칼(Kruskal) 최소 스패닝 트리 알고리즘 크루스칼 알고리즘은 모든 간선을 저장한..

문제 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://algospot.com/judge/problem/read/DRUNKEN algospot.com :: DRUNKEN Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day, algospot.com 풀이 종만북 난이도: 중 알고스팟 사이트에는 영문의 문제로 나와있어 당황했지만 종만북의 문제와 동일한 문제가 맞다. ..