Algorithm197 DFS, BFS 구현 방법 코드랑 원리를 아예 다 외워버리자!!! 출처: 강의 - 그래프 - 02. 그래프 순회: DFS와 BFS 1. DFS 구현: 재귀 이용 2. DFS : 스택 이용 함수 반환값( vector )은 dfs 함수에서 정점들이 방문한 순서를 정수형 벡터 형태로 반환 visited: 각각 정점 방문 여부 기록 visit_order: 각각 정점 방문 순서 기록 3. BFS : 큐 이용 #include #include #include #include #include using namespace std; const int N = 6; bool gVisited[N] = {}; void dfs_recursion(const vector& adj_list, int s) { if (gVisited[s]) return; gVisi.. 2022. 6. 16. [백준 2178] 미로 탐색 2178번: 미로 탐색 (acmicpc.net) 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 배운것 - (1,1)에서 (N,M)으로 가는 가장 빠른 길을 구하는 문제 - DFS로 못푼다 - BFS 탐색을 사용해야 한다 - BFS는 단계별로 진행된다는 사실을 이용 - BFS는 최단거리도 함께 의미 내 풀이 #include #include #include #include using namespace std; int a[100][100]; int d[100][100]; bool check[100][100]; int dx[] = { 0, 0, .. 2022. 6. 14. [백준 2667] 단지번호붙이기 2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 배운것 scanf("%1d",&a[i][j]); 쓰는 경우: 정수가 띄어쓰기 없이 입력 받을 때 cin으로 입력이 어렵다. 이때 %1d를 사용하면 붙어있어도 한번에 한개 씩 입력받을 수 있다. sort array 사용법 BFS #include #include #include using namespace std; int a[30][30]; int group[30][30]; int dx[] = {0,0,1,-1}; .. 2022. 6. 14. [백준 11724] 연결 요소의 개수 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net DFS 이용해서 푸는건데 구현하는거 익숙하지 않음.. 디버깅 하면 알겠는데 이걸 내가 구현할 수 있는가,,, #include #include using namespace std; vector a[1001]; bool check[1001]; void dfs(int node) { check[node] = true; for (int i=0; i 2022. 6. 13. [백준 11399] ATM 11399번: ATM (acmicpc.net) 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 어려웠던 점 int들 여러개 입력 받을때 변수랑 담는 형태 어떻게 줬는지 생각이 안남 -> 그냥 해주면 됨. 바로 입력 넣어주고.. #include #include #include using namespace std; int main(void) { int n; cin >> n; vectorline; for (int i = 0; i > k; line.push_back(k); } sort(line.begin(.. 2022. 6. 4. [백준 1260] DFS와 BFS 1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이건 디버깅 해보면서 하나하나 따라가며 여러번 보는게 답인듯 응용 문제 코드 복붙해서 푸는 연습 하기! 인접 리스트 풀이 #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; void dfs(int node) { check[node] = true; .. 2022. 6. 4. 이전 1 ··· 19 20 21 22 23 24 25 ··· 33 다음
