목록알고리즘/Graph (DFS, BFS) (24)

매일 조금씩

백준 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
백준 7576번 : 토마토

BFS를 사용한 문제다 고려해야할 부분이 많아서 다소 까다로운 문제였다. 1. 1은 익은 토마토, 0은 안익은 토마토, -1은 토마토가 없음 ( 대각선은 영향을 받지 않는다.) 2. 트리를 생각햇을 때 익을 수 있는것이 다 익어서 트리가 완성 되었을 때의 트리의 레벨 수가 익기까지 걸린 일 수. 3. 익은상태로 시작하는 토마토가 여러개일 수도 있음 (토마토상태 입력받으면서 deque에 1인 토마토 push 필요) 4. 토마토가 비어있는 곳(-1)이 있을 때, 다 익을수도 있고 아닐수도 있음 --> 다익었는지 확인하는 함수 따로 필요 #include #include //#include //memset using namespace std; const int MAX = 1000; typedef struct {..
알고리즘/Graph (DFS, BFS) 2020. 8. 7. 19:14
백준 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
백준 2178번 : 미로탐색

BFS를 활용한 간단한 문제이다. queue를 사용해서 풀었는데.. BFS를 공부한지 오래되어 가물가물해서 자주가는 '꾸준함' 티스토리를 참고하여 작성했다. https://jaimemin.tistory.com/508 백준 2178번 미로 탐색 문제 링크입니다: https://www.acmicpc.net/problem/2178 전형적인 BFS 문제였기 때문에 큐를 이용하여 쉽게 풀 수 있는 문제였습니다. 중요한 부분은 해당 칸과 이동하는 칸을 모두 방문 표시 처리해야한 � jaimemin.tistory.com #include #include #include #include //memset using namespace std; const int MAX = 100; int N, M; int maze[MAX][..
알고리즘/Graph (DFS, BFS) 2020. 8. 7. 01:37
백준 2606번: 바이러스

DFS, BFS, Union-Find를 사용하여 풀수 있는 문제다. 1. DFS(재귀) #include #include #include //memset using namespace std; const int MAX = 100 + 1; int N, M; int adjacent[MAX][MAX];// 1이면 연결됨을 의미 bool visited[MAX]; int cnt; // DFS 재귀 void DFS(int v) { cnt++; for (int i = 1; i > N >> M; for (int i = 0; i > from >> to; adjacent[from][to] = 1; adjacent[to][from] = 1; } visited[1] = 1;..
알고리즘/Graph (DFS, BFS) 2020. 5. 1. 21:25
백준 1260번: DFS와 BFS

DFS와 BFS에 관한 개념문제라고 볼수 있다. 아래 포스팅을 보고 풀었다. https://jaimemin.tistory.com/561 백준 1260번 DFS와 BFS 문제 링크입니다: https://www.acmicpc.net/problem/1260 자료구조 시간에서 다루었던 BFS(Breadth First Search)와 DFS(Depth First Search)를 복습할 겸 풀어봤던 문제였습니다. 실제로 BFS와 DFS는 자주 다루어.. jaimemin.tistory.com DFS는 재귀를 사용하여 풀었고 BFS는 큐를 사용하여 풀었다. #include #include #include //memset using namespace std; const int MAX = 1000 + 1; int N, M..
알고리즘/Graph (DFS, BFS) 2020. 5. 1. 20:33
이전 Prev 1 2 3 4 Next 다음