dfs

[골4] 14500 - 테트로미노

#include #include #include #include #include using namespace std; using ll = long long; #pragma region 상하좌우 / 위치 const pair dir[] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }, }; #define _y first #define _x second #pragma endregion #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define MAX 501 vector vis; vector ma..

[골4] 1405 - 미친 로봇

#include #include #include using namespace std; using ll = long long; #pragma region 상하좌우 / 위치 const pair dir[] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }, }; #define y first #define x second #pragma endregion #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define SIZE 4 double arrProb[SIZE]; double simple; int n..

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) / 장단점, 구현 및 시간복잡도

DFS의 장/단점 장점 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능) DFS의 구현 그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다. 인접 행렬로 구현했을 경우 [시간복잡도] DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로 n*O(n)이므로 O(n..

[골4] 1967 - 트리의 지름

#include #include #include using namespace std; #define MAX 10002 vector node[MAX]; bool vis[MAX]; int res, endPoint; void DFS(int p = 1, int len = 0) { if (vis[p]) return; vis[p] = true; if (res ..

[골5] 15686 - 치킨 배달

#include #include #include #include #include using namespace std; using IntPair = pair; #define y first #define x second vector board; vector house, chicken; int m, n, res = 0; bool vis[13]; int distance(IntPair a, IntPair b) { return abs(a.y - b.y) + abs(a.x - b.x); } void DFS(int start = 0, int end = 0) { if (end == m) { int tmpRes = 0; for (int i = 0; i < house.size(); i++) { int dist = INT_M..

[골4] 14502 - 연구소

참고해서 코드 작성 #include #include #include #include #define y first #define x second using namespace std; using IntPair = pair; using TwoDVec = vector; IntPair dir[] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; TwoDVec m, vm; vector vis; int h, w, ans = 0; // 바이러스 지도 초기화 함수 void SetMap() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) vm[i][j] = m[i][j]; } } void SpreadVirus() { queue q;..

[실2] 11725 - 트리의 부모 찾기

#include #include #include #include using namespace std; #define MAX_SIZE 100001 vector graph[MAX_SIZE]; int arr[MAX_SIZE]; bool vis[MAX_SIZE]; int main() { int n; cin >> n; for (int i = 1; i > y >> x; graph[y].push_back(x); graph[x].push_back(y); } stack s; s.push(1); vis[1] = true; while (!s.empty()) { auto idx = s.top(); s.pop(); for (int i = 0; i < graph[idx].size(..

유향 비순환 그래프 (DAG = Directed acyclic graph) 와 Khan 알고리즘을 이용한 위상 정렬 (Topological Sort)

DAG에 대한 토폴로지 정렬 알고리즘 위상 정렬이란 방향이 있는 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 나열하는 것이다. 싸이클이 없는(DAG, Directed Acyclic Graph) 그래프에선 가능하며 하나의 유향 그래프에서 여러 위상 정렬이 가능하다. 시간 복잡도 : O(V + E) / V (Vertex) : 노드, E (Edge) : 간선 => Best Case, Worst Case 동일. DFS와 관련된 다양한 유형의 에지의 출발 시간 사이의 관계이다. Tree edge (u, v): departure[u] > departure[v] Back edge (u, v): departure[u] < departure[v] Forward edge (u, v): dep..

C++ 그래프를 이용한 BFS / DFS 계속 업데이트할 예정

출처 : https://www.youtube.com/watch?v=tWVWeAqZ0WU 첫번째 문제 #include #include #include #include #include using namespace std; #define TOTAL_SIZE 1000 #define y first #define x second vector graph[TOTAL_SIZE]; bool visited[TOTAL_SIZE]{ false }; int edge = 0; void DFS(int _start) { cout

깊이 우선 탐색 BFS / 너비 우선 탐색 BFS 개념

깊이 우선 탐색 (DFS; Depth First Search) 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘을 의미한다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행한다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색 하는 것이다. 빠르게 모든 경우의 수를 탐색하고자 할 때 사용한다. 스택 이나 재귀함수 로 구현한다. 너비 우선 탐색 (BFS; Breadth First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색 하는 알고리즘이다. 즉, 깊게 (deep) 탐색하기 전에 넓게 (wide) 탐색 하는 것이다. 두 ..