알고리즘

문제 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 최악의 경로에서는 내리막길보다 오르막길을 우선으로 선택하며, 최적의 경로는 내리막길을 우선으로 선택한다. 오르막길은 C가 0이므로, 간선을 내림차순으로 정렬하여 크루스칼 알고리즘을 실시하면 최악의 경로를 구할 수 있다. 최적의 경로는 반대로 간선을 오름차순으로 정렬하여 크루스칼 알고리즘을 실시하면 얻을 수 있다. 코드 #include #include #include using na..

문제 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘, 정렬 문제에서 행성 사이의 가중치 후보는 x좌표, y좌표, z좌표의 차의 절댓값이다. 행성의 수는 최대 100,000개 이므로 각 행성에서 다른 모든 행성에 대해 탐색한다면 시간초과와 메모리 초과가 발생한다. 그러므로, 행성 사이의 가중치 후보를 줄여서 계산해야 한다. 행성 사이의 거리는 x, y, z 좌표 차이 중 최솟값이므로, 각 좌표를 나눠서 처리한다. A, B, C 행성의 ..

문제 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 직접 작성한 코드는 모든 노드의 부모 노드가 발전소 노드일 때까지 크루스칼 알고리즘을 진행하며, 각 노드가 이미 발전소와 연결되어있는 간선은 선택하지 않는 방식으로 작성했다. 다른 코드를 보니, 발전소 노드를 미리 하나의 그룹으로 묶어서 크루스칼 알고리즘을 진행하는 방식으로 문제를 해결하였다. 이렇게 하면 모든 노드가 발전소와 연결되었는지 확인할 필요도 없고, 한..

문제 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 미리 입력받은 학교의 성별에 따라, 간선이 입력되어야 하는 간선인지 아닌지를 선별한다. 간선의 각 학교의 성별이 서로 다른 성별일 경우에만 입력을 받는다. 입력받은 간선으로만 크루스칼 알고리즘을 실시한다. 연결된 간선의 수가 (학교의 수 - 1)보다 작다면 모든 학교가 연결되지 않았다는 뜻이므로, -1을 출력한다. 코드 #include #include #includ..

문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 너비 우선 탐색, 구현, 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 문제의 2차원 배열에서 각 섬은 너비 우선 탐색으로 섬의 수와 위치를 파악할 수 있다. 배열에 섬의 위치와 섬의 번호를 설정하였다면, 섬과 섬 사이의 간선의 길이를 파악해야 한다. 섬의 모든 점에서 부터 상하좌우로 움직이며 다른 섬에 도달하였을 경우 거리를 파악하여 간선으로 vector에 넣는다. 점의 수가 최대 100이므로 시간초과는 발생하지 않는다. 해당 ..

문제 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 다른 최소 스패닝 트리 문제와 달리, 간선이 아닌 노드를 입력으로 받는다. 그러므로 각 노드에서 다른 노드로의 간선을 구해야 한다. 간선의 비용은 노드끼리의 거리이다. 모든 간선을 구한 다음 크루스칼 알고리즘으로 최소 스패닝 트리를 만든다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2; float dis..

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. [백준][C++] 1197: 최소 스패닝 트리 문제 풀이 크루스칼 알고리즘을 이용하였다. 가중치가 작은 순서대로 검사할 수 있도록 간선을 가중치의 오름차순으로 정렬한다. 검사하는 간선이 사이클을 만들지 않다면 간선을 선택한다. 간 kantatatam.tistory.com 최소 스패닝 트리, 크루스칼 알고리즘의 기본 문제로 위의 문제와 풀이가 같다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2..

문제 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 다익스트라 문제이다. 다익스트라를 한번 실시하고, 최단 경로를 제거한 다음, 다시 다익스트라를 한번 실시하는 방식으로 풀어야 한다. 처음에는 최단 경로를 모두 제거될 때까지 반복해서 다익스트라를 실시 -> 경로 제거를 실시하였다. 이렇게 계속해서 다익스트라를 실시하면 시간초과가 발생한다. 한번의 다익스트라로 최단 경로를 모두 표시할 수 있도록 path 배열을 사용하였다. if (next_dist < dist[next_no..

문제 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net 풀이 다익스트라, 우선순위 큐 문제이다. 처음에는 특정 노드에 도착할 때마다 벡터에 현재 비용을 추가하는 방식으로 접근했다. 하지만 이렇게 하면, 특정 노드에는 k번 도달하지 않고 다익스트라가 종료될 수 있다. 그렇다고, 노드에 도착할 때마다 다익스트라를 돌리는 우선순위 큐에 값을 추가하면 다익스트라가 끝나지 않는다. 다익스트라에 추가적으로 우선순위 큐(내림차순)를 추가하여 풀 ..

문제 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 다익스트라에 경로 추적을 결합한 문제이다. 처음 문제를 읽었을 때, 최소 스패닝 트리 문제인줄 알았지만 최소 스패닝 트리로 접근할 경우 문제의 두번째 조건이 만족하지 않는다는 것을 알았다. 최소 스패닝 트리로 네트워크를 만들었을 때는 그래프의 가중치의 합이 최소인 그래프가 만들어지지, 최단 경로로 그래프를 만들어 주지는 않을 수 있다. 그러므로, 다익스트라로 접근하였고 필요한 것은 최단 거리가 아니라 연결된 간선이 필요하므로..