다락방

알고리즘DFS루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법스택 or 재귀함수를 통해 구현한다.모든경로를 방문해야 할 경우 사용에 적합하다.시간복잡도인접 행렬 : O(V^2)인접 리스트 : O(V+E)V(Vertex) : 정점, E(Edge) : 간선BFS루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법큐를 통해 구현한다.최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합하다.시간복잡도인접 행렬 : O(V^2)인접 리스트 : O(V+E)동적 계획법(Dynamic Programming)복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다.한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다.똑같은 연..

15886 내 선물을 받아줘 2 #include using namespace std; vector adj(1001); int visited[1001]; string move_s; void dfs(int x) { if (visited[x]) return; visited[x] = 1; if (move_s[x] == 'E') dfs(x+1); else dfs(x - 1); } int main() { int block, ans = 0; cin >> block >>move_s; for (int i = 0; i < move_s.size(); ++i) { if (!visited[i] && move_s[i] == 'E') { dfs(i); ++ans; } } cout

10451 순열 사이클 #include using namespace std; vector adj(1001); int visited[1001]; void dfs(int x) { visited[x] = 1; if (!visited[adj[x]]) { dfs(adj[x]); } } int main() { int test_case, node, max = 0, check; cin >> test_case; for (int i = 0; i > node; memset(visited, 0, sizeof(visited)); for (int j = 1; j > tmp; adj[j] = tmp; } check = 0; for (int j = 1; j

3182 한동이는 공부가 하기 싫어! #include using namespace std; vector adj(1001); int visited[1001]; int ans; void dfs(int x) { visited[x] = 1; if (!visited[adj[x]]) { dfs(adj[x]); } } int main() { int test_case, max = 0, check, ans; cin >> test_case; for (int i = 1; i > tmp; adj[i] = tmp; } for (int i = 1; i

1012 유기농 배추 #include using namespace std; const int MAX = 51; int test_case, m,n,k; int board[MAX][MAX]; int visited[MAX][MAX]; int dy[] = { 0,0,-1,1 }; int dx[] = { -1,1,0,0 }; void DFS(int y, int x) { visited[y][x] = 1; for (int i = 0; i = m || ny = n) continue; if (board[ny][nx] == 1 && visited[ny][nx] == 0) { DF..

1260 DFS와 BFS #include using namespace std; vector adj[10002]; vector result_bfs; vector result_dfs; bool visited[1002]; void dfs(int x) { visited[x] = true; result_dfs.push_back(x); for (int i = 0; i < adj[x].size(); ++i) { if (!visited[adj[x][i]]) dfs(adj[x][i]); } } void bfs(int x) { queue q; q.push(x); visited[x] = true; while (!q.empty()) { int tmp = q.front(); q.pop(); result_bfs.push_back..

DFS(Depth-First Search) 깊이 우선 탐색 알고리즘 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘 DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다.) 동작과정 탐색 시작노드를 스택에 삽입 후 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다. 2를 수행할 수 없을때까지 반복한다. def DFS(graph,v,visit): visited[v] = True print(v) for i in graph[v]: if not visited[i]: DFS(graph,i,vi..