🤔 의미
그래프란 “여러 개체들이 연결되어 있는 자료구조”이고 이 개체들 중에서 특정 개체를 찾는 즉, 탐색하는 알고리즘이라고 그래프 탐색 알고리즘이라고 불리는 것이다.
🏃 대표적인 문제 유형
경로 탐색 유형: 최단거리, 최소시간네트워크 유형(연결): 연결되어있는 그룹의 개수, 두 개체가 같은 그룹에서 연결되어 있는지조합 유형: 여러가지 조합 전부 만들고 비교
📓 구현 방법
가. DFS 최적
재귀 함수(일반적): 재귀를 타고 타서 탈출 조건 도달, 파라미터 변경
나. BFS DFS의 한 조합이 시간이 너무 걸릴 때 사용하면 용이
Queue, LinkedList: 여러 놈을 한대씩 때리면서 가는 유형
💻 느낀 점
DFS와 BFS는 매 CT마다 한 문제씩 나오기 때문에 잘 준비해야 하는 알고리즘 중에 하나이다. DFS BFS보다 시간이 적게 걸릴 수도 있다. 왜냐하면 하나의 경우를 빨리 찾으면 그것을 정답으로 바로 채택할 수 있기 때문이다. BFS는 물론 모든 경우를 한 단계씩 따지느라 시간이 좀 더 걸린다. 따라서 아예 DFS가 시간이 오래걸린다면 BFS로 바꿔서 푸는 시도도 해봐야한다. 물론 지금 큐와 링크드 리스트로 BFS를 푸는 방법을 몰라서 공부를 더 해야겠지만 말이다.
📝 출처
새끼 고양이 키우고 싶다