DDijkstra's Record DDijkstra's Record

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸..

다룰 내용 Dijkstra 알고리즘 벨만 포드 알고리즘 Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해가면서 최단 경로를 구하는 알고리즘으로 탐욕 기법을 이용하는 Prim 알고리즘과 유사합니다. 그러나 다익스트라의 경우 근시안적인 관점 때문에 음의 가중치가 있다면 사용할 수 없습니다. Dijkstra import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Dijkstra { public static class Vertex implements Comparable{ int v, weight; public Vert..

다룰 내용 신장 트리란 무엇인가? 최소 비용 신장 트리란 무엇인가? 최소 비용 신장 트리를 구성하는 방법 Kruskal 알고리즘 Prim 알고리즘 신장 트리란 무엇인가? 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다. 사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다. 최소 비용 신장 트리란 무엇인가? 신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다. 최소 비용 신장 트리의 특징 무방향 가중치 그래프입니다. 가중치의 합이 최소입니다. 정점 n개에서 n - 1개의 간선을 가지는 트리입니다. 사이클이 포..

다룰 내용 조합이란 무엇인가? 조합 구현 부분 집합이란 무엇인가? 부분 집합 구현 조합이란 무엇인가? 순서의 의미가 없이 수를 나열하는 것으로, 순열의 경우 순서가 의미가 있으나 조합은 의미가 없습니다. 조합을 구현하는 방법 현재 자리에서 조합할 수를 선택합니다. 조합 구현 첫 번째 방법 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Combination { public static int N, R; public static int origin[], number[]; public static void main(Strin..

다룰 내용 그래프란 무엇인가? 그래프의 종류 그래프를 표현할 수 있는 방법 그래프란 무엇인가? 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조를 의미합니다. 그래프의 종류 무향그래프: 간선의 방향이 없는 그래프입니다. 유향그래프: 간선의 방향이 있는 그래프입니다. 가중치 그래프: 정점에서 정점으로 이어진 간선에 가중치가 있는 그래프입니다. 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph): 사이클이 존재하지 않는 유향 그래프를 말합니다. 완전 그래프: 정점들에 대해 가능한 모든 간선들을 가진 그래프입니다. M개의 정점을 가지는 완전 그래프는 최대 M(M - 1) / 2 간선 수를 가집니다. 부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프입..

다룰 내용 Priority Queue란 무엇인가? Priority Queue 구현 방법 PrioriyQueue의 우선 순위 기준 부여하기(Java) - Comparable, Comparator Priority Queue란 무엇인가? 우선 순위에 따라 데이터가 추출되는 자료구조입니다. 따라서 들어간 순서에 상관없이 우선 순위가 높은 데이터가 먼저 추출됩니다. Prioriy Queue를 구현하는 방법 배열로 구현하는 방법 연결 리스트로 구현하는 방법 Heap을 이용하는 방법 배열로 구현하는 방법 구현하는 방법은 간단하나 데이터 삽입 및 삭제가 일어날 때마다 당기거나 미는 연산을 계속해서 연산이 많다는 단점이 있습니다. 또한 들어오는 데이터의 삽입 위치를 결정하기 위해 저장되어 있는 모든 데이터들과 우선 순위..

다룰 내용 순열이란 무엇인가? 순열 구현 next_permutation이란 무엇인가? next_permutation 구현 순열이란 무엇인가? 순서 있게 수들을 나열하는 것으로, 원소의 순서가 의미있다면 순열입니다. 서로 다른 N개의 수 중에 R개를 선택하여 나열(nPr)로 표현할 수 있고 경우의 수를 구하면 nPr = n * n - 1 * n - 2 ~~ n - r + 1 이렇게 구할 수 있습니다. 순열을 구현하는 방법 각 자리에서 앞 쪽에 선택된 수를 배제합니다. (앞쪽에서 선택된 수를 알기 위해 boolean 배열 사용) 현재 자리에서 선택 가능한 수를 선택합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.In..