본문 바로가기

알고리즘5

[C++] 백준 4963 섬의 개수 [Silver2] https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 풀이 1. 완전탐색을 통해.. 2023. 1. 21.
[Algorithm] 다익스트라(Dijkstra) 1. 다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘 2. 가중치 그래프에서, 임의의 점에서 목표점까지의 최소 비용 거리를 탐색할 수 있다. 3. 현재 점과 연결된 노드 중, 가중치가 가장 작은 노드를 선택 방문하여, 시작점으로부터 그 점까지의 거리를 업데이트 한다. 4. 3번 과정을 반복하면서, 특정 노드를 직접 방문했을 때 보다, 다른 점을 거쳐서 왔을 때의 거리가 작다면, 그 거리를 업데이트 하게 된다. 우선순위 큐 사용 알고리즘 1. 가중치 그래프를 저장하기 위한 구조체와 우선순위 큐(최소 힙)를 선언한다. 벡터를 사용해 구현할 시, 최소 가중치 노드를 찾기 위한 for loop 가 필요한데, 최소힙을 사용하면 이 과정을 O(log N)으로 줄일 수 있다. 2. 우선순위 큐에 시작점을.. 2023. 1. 21.
[C++] 백준 1753 최단경로 [Gold4] 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 풀이 시작점에서 다른 모든 정점으로의 최단 경로는 다익스트라 알고리즘으로 구할 수 있다. BFS 와 비슷하며 알고리즘 개념은 다음과 같다. 다익스트라 알고리즘 1. 현재 노드와 연결된 노드를 찾으면서 누적 거리 값을 계산한다. 2. 연결된 노드가 가지고 있는 거리 값이 현재 누적된 거리값 보다 크다면, 현재 누적된 거리가 최단 경로 이므로 업데이트 한다. ( 기본적으로, 모든 노드는 무한대 값으로 거리 값이 초기화 되어있다.) 3. 다음으로, 현재 알고 있는 누적 거리 중 가장 최소인 정점을 선택해서 뻗어나간다. 4. 3번 과정에서 현재 누적 거.. 2023. 1. 20.
[Algorithm] Minimum Spanning Tree - Prim 1. Prim 알고리즘은 최소 신장트리를 우선순위 큐를 통해 찾는다. 2. BFS 알고리즘에서 그래프 가중치가 존재하는 경우라고 보면 될 것 같고, 우선순위 큐를 사용한다는 점 이외에 알고리즘은 동일하다. 3. 최소 힙을 통해 가중치가 가장 작은 간선부터 탐색해 나가고, 각 노드를 방문했는지 체크하는 과정을 통해 싸이클을 막을 수 있다. #include #include #include #include using namespace std; /* 최소 신장 트리 (MST) 1. Kruscal 알고리즘: Union-find 알고리즘을 활용 2. Prim 알고리즘: priority-queue */ int ch[30]; struct Edge{ int e; int val; Edge(int a, int b){ e=a.. 2023. 1. 19.
[Algorithm] Minimum Spanning Tree - Kruscal 최소 신장 트리(MST)를 찾는 알고리즘으로 Union-Find 아이디어를 활용한다. Union-Find 란 disjoint set을 찾기 위한 아이디어 이다. 전반적인 아이디어는 다음과 같고, 알고리즘은 아래 코드에서 확인하면 된다. Union(a, b): a, b 노드가 연결되어 있다면 a 가 b를 연결시킨다. 즉, a = 1과 b=2가 연결되어 있다면 unf[a] = b 이다. 이때, unf[ ] 는 연결된 노드를 표시하기 위한 배열이고, 자기 자신을 가리키도록 초기화 된다. 즉, unf[1] = 1, unf[2]=2, unf[3]=3 .... unf[n]=n 이다. 1 과 2 노드를 Union 시키기 위해, 각 노드가 가리키는 루트노드를 찾는 Find(n) 재귀 함수를 실행한다. Find 재귀함수.. 2023. 1. 19.

티스토리툴바