BFS

[골3] 2206 - 벽 부수고 이동하기 (최신화)

3차원 배열 / 메모리 많이 차지함#include #include #include #include #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); \}\#pragm..

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

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

[골5] 13549 - 숨바꼭질 3

#include #include #include #include #include using namespace std; using IntPair = pair; #define MAX 100001 bool vis[MAX]; int MinSec(int n, int k) { priority_queue q; // 경과 시간을 기준으로 우선순위 큐 (짧을수록 우선순위 크다) q.push({ 0, n }); vis[n] = true; while (!q.empty()) { auto top = q.top(); q.pop(); int curSec = top.first, curLoc = top.second; // 목적지 도달 if (curLoc == k) return curS..

[골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;..

[골5] 7569 - 토마토

#include #include #include #include #include #include #include #include using namespace std; using int_pair = pair; #define SIZE 1000 #define y first #define x second // 윗층 뒤 우 아래층 잎 좌 pair arr_pos[] { {1, {0, 0}}, {0, {-1, 0}}, {0, {0, 1}}, {-1, {0, 0}}, {0, {1, 0}}, {0, {0, -1}} }; vector graph; // w:넓이, h:높이, l:층수 int w, h, l; queue q; void BFS() { #define ARR_POS_SIZE 6 while (!q.empty()) { ..

[골5] 7576 - 토마토

#include #include #include #include #include #include #include #include using namespace std; using int_pair = pair; #define SIZE 1000 #define y first #define x second // 상 하 좌 우 int_pair arr_pos[] { { 1, 0}, {-1, 0}, {0, -1}, {0, 1} }; vector graph; // w:넓이, h:높이, k:테스트 개수 int w, h, k; queue q; void BFS() { while (!q.empty()) { auto front = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int n..

[실1] 2583 - 영역 구하기 bfs

#include #include #include #include #include using namespace std; using int_pair = pair; #define SIZE 1000 #define x first #define y second // 상 하 좌 우 int_pair arr_pos[] { {0, 1}, {0,-1}, {-1,0}, {1, 0} }; queue q; bool graph[SIZE][SIZE]{ false }; int zone = 0; // w:넓이, h:높이, k:테스트 개수 int w, h, k; int BFS() { int block_cnt = 0; while (!q.empty()) { auto front = q.front(); q.pop(); for (int i = 0..

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) 탐색 하는 것이다. 두 ..