Problem Solving4 Union-Find 알고리즘 union은 x의 집합과 y의 집합을 합치는 과정이다. find는 x가 어떤 집합에 속하는지를 판별하는 과정이다. 소스를 짜기전에 parent[]라는 배열이 있어야합니다. (x의 부모는 y이다 parent[x] = y) 또한 초기설정으로는 노드의 갯수에 따라서 parent[i] = i로 초기화를 시켜줍니다. void setUnion(int x, int y) { x = getFind(x); y = getFind(y); if (x != y) { parent[y] = x; } } x와 y가 각각 어떤 집합에 속하는지를 찾아주고, x와 y가 같지 않다면 parent[y] = x; 를 하여 집합을 합치는 작업을 해준다. int getFind(int n) { if (parent[n] == n) return n; /.. 2020. 4. 2. 다익스트라 알고리즘 (Dijkstra Algorithm) 개념정리 다익스트라 알고리즘이란? 다익스트라 알고리즘같은 경우에는 가중치가 있는 그래프의 최단경로를 찾을 때 사용 된다. 1. 다익스트라 알고리즘은 연결 단순 비방향성 가중치 그래프에서 두 정점 간의 최단경로의 길이를 구한다. 2. 다익스트라 알고리즘은 연결 단순 비방향성 가중치 그래프에서 두 정점 간의 최단경로의 길이를 구하는데 O(n*n) 연산을 사용한다. 구현 Vertax 갯수 Edge 갯수 vertax1 ~ vetax (연결) , 가중치 위의 변수와 우선순위큐를 이용해서 다익스트라 알고리즘을 구현할 수 있다. 2020. 3. 16. [백준] 백준 4179번 불! 백준 4179번 문제소개 먼저 BFS를 사용하여 풀 수 있는 문제 이다. https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간 www.acmicpc.net 백준 4179번 문제풀이 Input : 4 4 #### #JF# #. .#.. 2020. 3. 16. [백준] 백준 1924번 2007년 (C++) #include #include using namespace std; int month, day; string d[7] = { "SUN","MON", "TUE", "WED", "THU", "FRI", "SAT" }; void init() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int search(int i, int max) { int temp; for (int j= 1; j > month >> day; int sum = 0; for (int i = 1; i 2020. 3. 8. 이전 1 다음
