알고리즘/백준

문제 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 풀이 다익스트라에 경로 추적을 결합한 문제이다. 처음 문제를 읽었을 때, 최소 스패닝 트리 문제인줄 알았지만 최소 스패닝 트리로 접근할 경우 문제의 두번째 조건이 만족하지 않는다는 것을 알았다. 최소 스패닝 트리로 네트워크를 만들었을 때는 그래프의 가중치의 합이 최소인 그래프가 만들어지지, 최단 경로로 그래프를 만들어 주지는 않을 수 있다. 그러므로, 다익스트라로 접근하였고 필요한 것은 최단 거리가 아니라 연결된 간선이 필요하므로..

문제 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 다익스트라에 경로 추적을 결합한 문제이다. 출력 시, 각 집하장에서 다른 집하장까지의 최단 경로가 필요하므로 각 집하장마다 다익스트라를 실행해야 한다. 다익스트라 도중에 최단 경로가 갱신될 때, 현재 노드의 부모 노드를 갱신한다. next_node를 최단 경로로 도달하기 위해서는 current_node애서부터 와야 한다. 부모 노드를 추적하면 한 집하장에서 다른 집하장으로 최단 경로로 갈 때, 바로 다음 집하장을 알 수 있다. 코드 #include #inclu..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 풀이 다익스트라 문제이다. 도로를 하나의 그래프로 생각하는데 주목한다. 그래프의 노드는 바로 다음 노드와 거리가 1로 연결되어 있다. 위의 그래프에서 입력 받은 지름길을 추가한다. 역주행 할 수 없으므로, 지름길의 끝이 D를 넘어간다면 그래프에 추가하지 않는다. 지름길의 거리가 시작과 끝의 거리보다 길다면, 거리를 줄일 수 없으므로 그래프에 추가하지 않는다. 그래프를 0에서부터 다익스트라를 통해 D까지의 최소 거리를 구한다. 코드 #include..

문제 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라 문제이다. 첫 시도에는 s를 시작점으로 다익스트라를 한번 실시하고, 경로를 추적하여 시도하였지만, 메모리 초과가 발생하였다. 그리고 이 방법은 x까지의 최단 경로가 여러 개 존재할 경우, 답이 올바르지 않을 수 있다. s, g, h를 시작점으로 다익스트라를 세번 실시한다. s -> g -> h -> x로 가는 최단 경로의 비용이 s -> x로 가는 최소 경로의 비용과 일치한다면, 해당 최소 경로는 g -> h를 거친다고 볼 수 있다. ..