넘치게 채우기

https://www.acmicpc.net/problem/27945BOJ - 슬슬 가지를 먹지 않으면 죽는다문제 유형: 그래프, MST(최소 신장 트리), 분리 집합, 유니온 파인드문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제키위새는 가지와 사랑에 빠지면서 가지로 맛있는 요리를 하기 위해 1번부터 N번까지의 번호가 붙은 N개의 요리 학원에 다니기 시작했다.각 요리 학원 사이에는 총 M개의 양방향 길이 있고, i번째 길에는 정확히 ti일에만 문을 여는 가지 디저트 노점이 있다. (ti는 모두 다르다.) 아직 가지 요리를 배우는 중인 키위새는 직접 가지 요리를 해 먹지는 못하다 보니 가지 부족증(hypomelitzemia)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저..

https://www.acmicpc.net/problem/1119BOJ - 그래프문제 유형: 그래프, MST(최소 신장 트리), dfs/bfs문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제N개의 도시가 있고, 몇몇 도시들이 양방향 도로로 연결되어 있는 나라가 있다. 은진이는 이나라의 도로 몇 개를 수정해서 모든 도시가 서로 연결되어 있게 하려고 한다. 이때, 도로를 수정하는 회수를 최소로 하려고 한다. 도로를 수정하는 방법은 다음과 같다.A와 B가 연결되어 있고, C와 D가 연결되어 있으면서, A와 C, A와 D, B와 C, B와 D가 연결되어 있지 않은 4개의 도시 A, B, C, D를 선택한다.A와 B를 연결하는 도로와 C와 D를 연결하는 도로를 없앤다.A와 C, B와 D를 연..

https://www.acmicpc.net/problem/17472BOJ - 다리 만들기 2문제 유형: bfs/dfs, 그래프, MST, 최단경로, 구현문제 난이도: Gold I시간 제한: 1초메모리 제한: 1024MB 문제섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를..

https://www.acmicpc.net/problem/1922BOJ - 네트워크 연결문제 유형: MST(최소 신장 트리)문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 ..

https://www.acmicpc.net/problem/2887BOJ - 행성 터널문제 유형: MST(최소 신장 트리), 최단 경로, 그래프, 정렬, 이진 탐색문제 난이도: Platinum V시간 제한: 1초메모리 제한: 128MB 문제때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모..

https://www.acmicpc.net/problem/1197BOJ - 최소 스패닝 트리문제 유형: 최소 신장 트리, 최단 경로문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 ..

최소 신장 트리 (Minimum Spanning Tree, MST) 신장 트리는 그래프의 모든 정점을 연결하는 트리를 말한다. (사이클이 생기지 않음) 최소 신장 트리는 그래프의 모든 정점을 연결하는 간선들의 가중치의 합이 최소인 트리를 말한다. (신장 트리중 가장 저렴한 비용) 크루스칼 알고리즘(Kruscal's Algorithm) 크루스칼 알고리즘은 최소 신장 트리를 찾는 방법 중 하나이다. 1. 모든 간선들을 가중치 기준으로 오름차순 정렬한다. 2. 가장 작은 가중치의 간선부터 선택한다. 3. 고른 간선이 사이클을 형성한다면, 선택하지 않는다. 4. 2와3을 계속 반복한다. 아래는 크루스칼 알고리즘의 예시이다. 우선, 간선들의 가중치를 기준으로 오름차순 정렬해준다. A-B : 1 A-C : 2 B-..