목록dfs (8)

매일 조금씩

백준 2583번 : 영역 구하기 [C++]

DFS를 사용해서 풀었다. 빈칸의 넓이는 빈칸의 개수와 같으므로 cnt로 ++하면서 vector에 넣었다. #include #include //memset #include #include #include using namespace std; const int MAX = 100; typedef struct { int y, x; }dir; dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; int N, M, K; int graph[MAX][MAX]; bool visited[MAX][MAX]; queue q; int result, cnt; vector each; void BFS(int y, int x) { q.push(make_pair(y, x)); visited..
알고리즘/Graph (DFS, BFS) 2020. 8. 9. 20:26
백준 2468번 : 안전 영역 [C++]

DFS와 Brute Force를 사용하여 풀었다. 중요한 건, 영역의 높이는 최소 1이므로 영역의 높이가 모두 0이고 수위도 0이여서 안전영역의 수가 0만 나오는 경우는 없다는 것!! 모든 영역이 같은 숫자일 경우엔 안전 영역의 수가 0아니면 1 이므로 최댓값은 1이된다는 것이다. 예를 들어, 모든 영역이 1이라면 수위가 0일 땐 전부 안잠기므로 안전영역은 1개가 되고, 수위가 1이상이 되면 모두 잠겨서 안전영역은 0개가 된다. 즉, 1은 나올 수 있는 안전영역 수의 최솟값이 된다. 따라서, result의 초깃값은 1이다. 물의 높이가 따로 주어지지 않았기 때문에 입력을 받으면서 가장 낮은 영역과 가장 높은 영역을 따로 정의했다. 물높이는 입력 받은 영역의 높이에서 가장 낮은 높이 ~ 가장 높은 높이인 ..
알고리즘/Graph (DFS, BFS) 2020. 8. 9. 19:37
백준 6603번 : 로또 [C++]

DFS와 비슷하게 재귀를 활용하면 풀수 있는 문제였다. #include #include //#include //memset #include using namespace std; const int MAX = 6; int K; int lotto[MAX]; int t[13]; //idx1은 t의 인덱스, idx2는 lotto의 인덱스 void printLotto(int idx1, int idx2) { if (idx2 == MAX) { for (int i = 0; i t[i]; } printLotto(0, 0); cout
알고리즘/Graph (DFS, BFS) 2020. 8. 9. 16:59
백준 11724번 : 연결 요소의 개수 [C++]

BFS와 DFS 두가지를 모두 이용하여 풀수 있는 문제다. 1. DFS #include #include #include //memset #include using namespace std; const int MAX = 1000 + 1; int N, M; vector connect[MAX];// 이차가됨 bool visited[MAX]; void DFS(int node) { visited[node] = true; // node에 연결된 다른 정점을 모두 방문 for (int i = 0; i >..
알고리즘/Graph (DFS, BFS) 2020. 8. 8. 17:04
백준 1012번 : 유기농 배추 [C++]

DFS를 활용한 문제다. 기본 DFS에서 동서남북으로 붙어있는 배추들이 몇 세트 인지 세는 vector를 추가하면 된다. #include #include #include #include //memset using namespace std; const int MAX = 50; typedef struct { int y, x; }Dir; Dir moveDir[4] = { {1,0},{-1,0},{0,1},{0,-1} }; int T, N, M, K; int farm[MAX][MAX]; bool visited[MAX][MAX]; vector v; int cnt; void DFS(int y, int x) { visited[y][x] = true; for (int i = 0; i < 4; i++) { int nex..
알고리즘/Graph (DFS, BFS) 2020. 8. 8. 14:33
백준 2667번 : 단지 번호 붙이기

BFS와 DFS 두가지로 다 가능한 방법이다. 처음에 관련 포스팅을 참고하여 DFS로 푼후, BFS로도 풀어보았다. 1. 입력받은 N*N을 돌면서 1이고 방문하지 않은 곳일 경우 DFS or BFS함수를 호출한다. 2. 호출된 DFS함수는 '재귀'로 연결된 모든 곳을 찾으면서 cnt++하고 더이상 연결된 곳이 없어서 함수실행을 마친후엔 vector에 그 cnt(연결된 마을수)를 push_back 한다. 2-1. 호출된 BFS 함수는 '큐'로 연결된 모든 곳을 찾는다. while문 안에서 현재위치와 연결된 모든 곳을 큐에 넣고 현재위 치를 pop 한후의 front가 현재위치가 되어 연결된 곳이 더이상 없어 큐가 빌때 까지 반복한다. 1. DFS #include #include #include #includ..
알고리즘/Graph (DFS, BFS) 2020. 8. 7. 15:04
이전 Prev 1 2 Next 다음