다락방

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

14502 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #include using namespace std; const int mxN = 8, dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 }; int n, m, a[mxN][mxN]; int tmp[mxN][mxN]; int ans = 0; bool vis[mxN][mxN]; void copy(int tmp[mxN][mxN], int a[mxN][mxN]) ..

17130 토끼가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17130 17130번: 토끼가 정보섬에 올라온 이유 첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. '.'은 빈 공간을, '#'은 벽을, 'R'은 토끼를, 'C'는 당근을, 'O'는 정보섬 쪽문을 나타낸다. 'R'은 반 www.acmicpc.net #include using namespace std; int n, m, startY ,ans = 0; string s; int dp[1001][1001] = { 0, }; char _map[1001][1001]; bool check = false; void move() { for (int j = startY; ..

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

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..