DFS, BFS 총 정리

큰 틀에서 DFS, BFS를 잡아보도록 하자

나만의 언어로 정리하는게 좋을 듯 싶다.

1. 그래프

• 유형1. 양방향 탐색 DFS

백준1260 DFS와 BFS: [양방향 그래프 문제] 둘 다 visited와 시작점이 필요하다.
뽑을 때 위치가 중요한데 

지점 확인점
bfs: popleft를 할 때 그 지점이 확인된다고 생각하자
dfs: 새로 항상돌기 때문에 첫 지점 for문의 전 지점에 돈다고 생각하면 좋을 것 같다.

백준11724 연결요소의 개수: [양방향 그래프 문제] visited와 시작점을 기준으로 전부 다 돌기. 그래프계의 영역 구하기

dfs: 전체를 돌기 위해서 visited를 주고 False 걸린 것들을 다시 돌려주는 시스템

백준2606 바이러스: [양방향 그래프 문제] dfs cylce를 한번 걸렸을 때 요소의 개수를 확인하는 문제


백준11725 트리의 부모 찾기
백준1707 이분그래프

2. 테이블 --> 이거 너무 싫어! 근데 알아냈어!

• 유형1. visit 테이블을 아예 만들어 놓고 시작

백준3184 양: 
visit table을 만들어 놓고 방문했는지 아닌지를 쓰는 것이다
아이디어는 한 잉크를 떨어뜨려 그 안에 있는 물체들을 다 확인하는 편인 것이다
한번 bfs 가 돌게 되면 한 영역, 즉 # 안에 있는 것이 한번 싹 도는 것!