BOJ 문제풀이/깊이-너비우선탐색 (DFS-BFS) 썸네일형 리스트형 백준 9205 : 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 매우 간단한 BFS, DFS, 다익스트라, 플로이드-와샬 등으로 다양한 방법으로 풀 수 있다. 1. BFS나 DFS로 탐색할 경우 탐색이 끝난 후 visited[] 배열에 도착지가 true인가 false인가 확인하면 된다.2. 다익스트라로 탐색할 경우 탐색이 끝난 후 도착지 정점의 dist가 INF인지 아닌지 확인하면 된다.3. 플로이드-와샬로 탐색할 경우 탐색이 끝난 후 matrix[출발지][도착지]가 INF인지 아닌지 확인하면 된다. 기본적으로 1000m 이내에 있으면 간선으로 연결시켜주고 그 외의 경우에는 연결할 필요가 없다.또한 간선에 대한 가중치도 필요가 없다. 왜냐하면 콜라를 리필하는데 대한 비용같은 것은 염두에 두지 않기 때문.. 더보기 백준 2606 : 바이러스 https://www.acmicpc.net/problem/2606 간단하다. BFS로 풀어도 되고 DFS 로 풀어도 되고 심지어 플로이드-와샬을 써도 된다.그냥 단순히 그래프의 연결문제를 탐색하는 것. 숫자만 세는 것이므로BFS 나 DFS로 visited = true; 라고 새롭게 방문을 하는 순간count++ 해주면 된다. 1. 큐를 이용한 BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38#include #include #define MAX 101 using namespace std; int matrix[MAX][MAX]; bool visited[MAX]; i.. 더보기 백준 11581 : 구호물자 https://www.acmicpc.net/problem/11581 Cycle이 존재하는지 묻는 문제이다.그래프의 시작점은 1부터 시작해서 n까지 도착하는 것이고모든 그래프를 탐색하면서 도중에 Cycle이 돌면 안된다. Cycle이 도는지 검사하는 것은 여러가지 방법이 있지만이 문제에서는 이미 그래프가 주어졌고 그래프의 노드를 모두 탐색하는 것이므로DFS를 사용한다. Stack을 이용한 DFS도중에 만약 이미 visited한 점을 만났다면 그것이이전에 되돌아가서 visited 체크된것인지 아니면 이미 방문해서 visited가 된것인지 확인해야 한다. 만약 Stack에 이미 visited 체크된 노드가 존재한다면 이미 방문한 노드이기 때문에 cycle이 발생한다.만약 visited 체크된 노드이지만 Sta.. 더보기 백준 16397 : 탈출 https://www.acmicpc.net/problem/16397이번에 우리학교 코딩대회에 나갔다.. 복수전공 시작하고 아직 학교 수업은 자료구조를 듣는 터라알고리즘에 관한 지식은 구글링하며 독학하며 주워들은 것 밖에 없다. ABC 세문제 밖에 못풀었는데D와 K 2문제는 풀 수 있었을 것 같은데 아쉽게 계속 시간초과가 났다. (이 두 문제만 풀었어도..)어쨌든 반성하는 의미에서 시험장에서는 못풀었지만 더 공부하며 나머지 문제를 다 풀어보려한다. D번 문제였던 탈출은 시험장에서 계속 DFS밖에 생각이 안났다. 그것도 평소 DFS를 재귀로만 구현해서문제를 풀어봤던지라 스택으로 짜는 것은 아무생각이 안들었음. 이 문제를 시험 다다음날 구글에 검색해보았는데 BFS로 풀었다고 한 순간 머리가 띵해졌다.생각해보니.. 더보기 이전 1 다음