C++

BFS, DFS와 트리, 그래프에 대한 글..

시작하기에 앞서, 기초적인 구현 방식, 정보들은 최대한 글에서 다루지 않을 예정이고, 혼동되거나 헷갈리는 부분들, 놓치고 넘어가기 쉬운부분들만 설명할 것임을 유의해주세요..! 그래프 탐색이 필요한 이유는 바로 선형적인 탐색 (for문을 통한 i:1~n) 으로 탐색하지 못하는 문제들을 탐색하기 위해서이다. 예를들어 그래프 탐색이 필요한 문제중 하나인 백준 2178 "미로 탐색" 을 보자. 우리는 점차 증가하는 인덱스를 통한 탐색이 아닌, 갈 수 있는 위치로 향하는 탐색을 해야하는데, 이는 for문과 적합하지 않다. 그렇기에 우린 이러한 갈 수 있는 방향을 "그래프" 로 만들어나가며 탐색을 해나가는 것이다. 그래프의 대략적인 정의는 정점, 그리고 간선으로 이루어진 대충 아래 그림 같은 친구들을 말한다. 그래..