bfs와 dfs는 그래프 탐색 알고리즘으로, 문제를 풀 때 상당히 많이 사용한다. > 그래프란? 여러 개체들이 연결되어 있는 자료구조 > 탐색이란? 특정 개체를 찾는 것 대표적인 문제 유형 경로 탐색 유형 (최단거리, 시간) 네트워크 유형 (연결, 그룹 개수) 조합 유형 (모든 조합 구하기) DFS 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법 스택보다는 재귀함수를 통해 구현하는 것이 일반적이고, 재귀를 타고 타고 가서 탈출 조건에 먼저 도달하도록 한다. 모든 경로를 방문해야 할 경우 사용에 적합 시간 복잡도 인접 행렬 : O(V^2) 인접 리스트 : O(V+E) V는 접점, E는 간선을 뜻한다 BFS 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법 일반적으로 큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문) 가장 먼저 넣었던 것을 꺼내서 거기에

1. 깊이 우선 탐색 그래프 탐색은 하나의 정점을 시작으로 모든 정점을 한 번씩 방문하는 것이다. 깊이 우선 탐색(Depth-First Search)이란 그래프 탐색법의 일종으로, 한 정점에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 전부 탐색하는 방법이다. 주로 모든 노드를 방문해야 할 때 이 방법을 선택하며, 너비 우선 탐색(BFS)보다 간단하나 검색 속도는 느릴 수 있다. 불필요한 경우를 차단하는 등의 처리가 없기 때문에 경우의 수가 줄어들 수는 없다. 때문에 N!의 경우의 수를 가지는 문제는 DFS로 풀 수 없다. 또한 최단 경로를 구하는 문제의 경우 그 해는 최단 경로가 되지 않을 수 있다. 해에 도착하면 탐색을 끝내버리기 때문이다. 트리를 기준으로 보았을 때는 자식 노드의 자식 노드 끝까지 따라가 잎(leaf)를 만날 때까지 깊게 탐색하는 꼴이며, 미로 탐색의 예에서는 한 길로 쭉 가다가 더이상 진행할 수 없을 때 직전의 갈림길로 돌아가 다른

문제 해결 이 문제는 bfs로 풀면 간단한 문제다. 먼저 선입선출로 가장 빠른 길을 찾는 문제기 때문에 deque를 사용하여 구현한다. 그리고 한글자 차이인 단어를 찾아 차례대로 deque 에 넣고 바꾸고를 반복하며 원하는 단어가 나오는 가장 빠른 길을 찾는다.

프로그래머스 문제 이 문제는 미로 통과하는 경우의 수 중에, 가장 최단거리를 구하는 문제다. 일단 최단거리를 구하는 문제기 때문에 bfs 방식으로 구현하려고 했다. queue를 활용했고, 목적지에 도달하는 순간 바로 정답을 리턴한다. 아래는 첫번째 나의 솔루션인데, 해결되지 않았다. 디버깅 필요!!!

문제 이 문제는 네트 워크 상 컴퓨터끼리의 서로 연결 유무를 나타낸 lists 가 있을 때, 네트워크 덩어리가 몇 개인지 구하는 문제이다. 처음에는 감을 못 잡았지만, 천천히 고민하며 한 노드와 연결된 모든 노드를 재귀적으로 찾도록 dfs 방식을 활용하고, 다 찾은 경우에 개수를 +1 해주도록 작성했다. 여기서 visited가 필요한 이유는, 탐색 중에 걸리는 모든 노드는 재귀적으로 연결된 모든 노드를 확인하기 때문에 한번 본 노드는 볼 필요 없으므로 체크하기 위함이다. 아래는 solution이며 블로그를 참고하여 풀었다.

타켓넘버 이 문제가 왜 dfs/bfs 인지 처음에는 이해가 되질 않았다. 이 포스팅이 도움이 되었다. 모든 경우의 수의 합을 트리의 맨 마지막 노드라고 생각하면, 트리의 깊이인 idx 값을 숫자 개수와 비교하여 합을 체크하면 된다. 맨 마지막 노드가 아닐 경우에는 다음 숫자를 +- 한 값을 큐에 추가한다. 큐가 모두 빌 때까지 반복한다면, 모든 자식 노드를 확인한 셈이 될 것이다. 아래는 이해를 완료한 후 다시 작성한 solution이다.

DFS Root Node 혹은 다른 임의의 Node에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 끝까지 완벽하게 탐색하는 방법이다. Stack 혹은 재귀함수(Recursion)으로 구현된다. 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 시간 복잡도 - 접점(V), 간선(E) 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) BFS Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다. Queue를 사용해서 구현한다. 시간 복잡도 - 접점(V), 간선(E) 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 추가적으로 BFS로 효과적으로 풀 수 있는 문제들이 있다. 3가지의 조건을 만족