All-rounder developer

오늘의 학습 키워드DFS, BFS, 스택, 큐, 우선순위 큐 오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/1260 그래프를 DFS와 BFS로 탐색한 결과를 출력하는 문제이다.방문 가능한 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다. 🌱 나의 시도1. 인접 리스트 구현그래프를 나타내기 위해 우선순위 큐를 이용한 인접 리스트를 구현하였다.이 문제에서는 방문 가능한 정점이 여러 개인 경우 정점 번호가 작은 것부터 순회하여야 하기 때문에, 인접 리스트 내부 인덱스는 정렬된 상태로 유지되어야 한다. 우선순위 큐는 힙으로 구현되어 항상 정렬된 상태를 유지하며 삽입/삭제 시 O(log N)의 시간 복잡도를 가지므로, 리스트를 정렬하는 것보다 우선순위 큐를 ..

0. IntroductionDFS와 BFS를 별도 게시물로 정리하려고 했으나 결국 하나의 게시물로 정리하게 되었다.둘은 이름이 비슷해서인지 잘 헷갈리는 것 같다.같은 게시물 안에서 동일한 그래프로 비교하면서 보면 더 잘 이해할 수 있을 것이라고 판단하였다.단, BFS, DFS 문제풀이는 본 게시물에서 다루지 않는다. 앞으로 DFS, BFS 문제를 공부하면서 차근차근 하나씩 추가해보겠다. 1. DFS (Depth-First Search, 깊이 우선 탐색)1. 정의이름에서 알려주는 것처럼 깊이를 우선적으로, 즉, 가장 깊이 위치하는 노드까지 탐색하는 알고리즘이다.DFS 문제를 풀 때는 스택을 활용하면 더 쉽게 해결할 수 있다.이것은 예시를 보면 더욱 잘 이해할 수 있으니 예시를 함께 보면서 확인하도록 하자...